Leetcode 2844: Minimum Operations to Make a Special Number
You are given a non-negative integer represented as a string num. In one operation, you can remove any single digit from the string. If you remove all digits, the result becomes 0. Your task is to return the minimum number of operations required to make the number divisible by 25. A number is divisible by 25 if it ends in 00, 25, 50, or 75.
Problem
Approach
Steps
Complexity
Input: The input is a string num representing a non-negative integer.
Example: num = "78492"
Constraints:
• 1 <= num.length <= 100
• num only consists of digits '0' through '9'.
• num does not contain any leading zeros.
Output: Return the minimum number of operations required to make num divisible by 25.
Example: 2
Constraints:
• The output should be a single integer representing the minimum number of operations.
Goal: To find the minimum number of operations to make the number divisible by 25.
Steps:
• Loop through the digits of the number from the end (rightmost side).
• Check if the current digits can form a valid pair (00, 25, 50, or 75).
• Track if '0' and '5' are found to make possible combinations.
• Count and remove digits to form a number ending in one of the valid pairs.
Goal: The input string follows these constraints:
Steps:
• 1 <= num.length <= 100
• The string contains only digits '0' to '9'.
• No leading zeros are allowed in the input.
Assumptions:
• The string will always represent a valid non-negative integer.
• Input: num = "78492"
• Explanation: The number 78492 is not divisible by 25. To make it divisible by 25, delete digits 4 and 9 to get 780, which ends in 00, making it divisible by 25.
• Input: num = "12000"
• Explanation: The number 12000 is divisible by 25 if the last two digits are kept. Delete digits 2 and 3 to get 1200, which ends in 00, making it divisible by 25.
• Input: num = "4510"
• Explanation: The number 4510 can be made divisible by 25 by removing digit 1. The resulting number 450 ends in 50, making it divisible by 25.
Approach: We iterate through the digits of the number from the end to check if we can form one of the valid endings (00, 25, 50, 75). The goal is to find the minimum number of deletions to make the number divisible by 25.
Observations:
• We need to find the two digits that make the number divisible by 25.
• Valid endings are 00, 25, 50, or 75.
• We can scan the number from right to left, keeping track of the digits we find to form the required pairs.
Steps:
• Loop through the digits of num from the end.
• Check if the current digits can form any of the valid pairs (00, 25, 50, or 75).
• Count how many deletions are required to form a valid pair.
Empty Inputs:
• There are no empty inputs as the string length is always at least 1.
Large Inputs:
• The solution should handle strings with lengths up to 100 efficiently.
Special Values:
• Consider cases where num is already divisible by 25 or has fewer than two digits.
Constraints:
• Ensure there are no leading zeros in the input.
int minimumOperations(string num) {
bool fivefound = false;
bool zerofound = false;
for (int i =num.size()-1; i >=0;i--) {
if (zerofound && num[i]=='0') return num.size()-2-i;
if (zerofound && num[i]=='5') return num.size()-2-i;
if (fivefound && num[i]=='2') return num.size()-2-i;
if (fivefound && num[i]=='7') return num.size()-2-i;
if (num[i]=='5') fivefound = true;
if (num[i]=='0') zerofound = true;
}
if (zerofound) return num.size()-1;
return num.size();
}
1 : Function Declaration
int minimumOperations(string num) {
Declare the function `minimumOperations` that accepts a string `num` representing a number and returns the minimum number of operations to make the number divisible by 25.
2 : Variable Initialization
bool fivefound = false;
Initialize a boolean variable `fivefound` to track if the digit '5' has been encountered.
3 : Variable Initialization
bool zerofound = false;
Initialize a boolean variable `zerofound` to track if the digit '0' has been encountered.
4 : Loop Setup
for (int i = num.size() - 1; i >= 0; i--) {
Start a loop that iterates over the digits of the number `num` in reverse order.
5 : First Condition Check
if (zerofound && num[i] == '0') return num.size() - 2 - i;
If '0' has been found earlier and the current digit is also '0', return the number of operations needed to form '00'.
6 : Second Condition Check
if (zerofound && num[i] == '5') return num.size() - 2 - i;
If '0' has been found earlier and the current digit is '5', return the number of operations needed to form '50'.
7 : Third Condition Check
if (fivefound && num[i] == '2') return num.size() - 2 - i;
If '5' has been found earlier and the current digit is '2', return the number of operations needed to form '25'.
8 : Fourth Condition Check
if (fivefound && num[i] == '7') return num.size() - 2 - i;
If '5' has been found earlier and the current digit is '7', return the number of operations needed to form '75'.
9 : Check for '5'
if (num[i] == '5') fivefound = true;
If the current digit is '5', set `fivefound` to `true`.
10 : Check for '0'
if (num[i] == '0') zerofound = true;
If the current digit is '0', set `zerofound` to `true`.
11 : Final Check for '0'
if (zerofound) return num.size() - 1;
If '0' has been found, return the number of operations needed to form '00'.
12 : Return Statement
return num.size();
Return the size of the number if no valid pair of digits was found.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we scan through the digits of the number once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we are only using a constant amount of extra space.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus