1. Overview
In this tutorial, we’ll see different algorithms allowing us to find the largest number possible after removing the k digits of a number.
First, we’ll explain the problem. Then, we’ll see two different algorithms that suit our needs. Finally, we’ll discuss their complexities.
2. Problem Explanation
First, let’s explain what the goal of the algorithm is. We want to find the largest number possible after removing the k digits of a number.
For example, consider the number 286281. The number of elements we must remove is 2, so the largest possible number will be 8681. Let’s say we consider another value of k, i.e. 2, so the expected output would be 88.
3. Using Arithmetic
In this section, we’ll see the logic explanation and time and space complexity.
3.1. Logic
Let’s see the logic that would help achieve our goal using some arithmetic. We’ll use the method findLargestNumberUsingArithmetic(num, k) to implement our logic that returns the resultant number.
The function findLargestNumberUsingArithmetic(n,k)Â takes two parameters: n (the original number) and k (the number of digits to remove):
public static int findLargestNumberUsingArithmetic(int num, int k) {
//...
return num;
}
We have an outer loop that iterates k times, representing the number of digits to remove:
for (int j = 0; j < k; j++) {
//...
}
For each iteration, it enters an inner loop to remove each digit once. The inner loop calculates the number formed after removing each digit once and compares it with the current maximum number:
while (num / i > 0) {
int temp = (num / (i * 10)) * i + (num % i);
i *= 10;
result = Math.max(result, temp);
}
num = result;
After removing the digit, it updates the maximum number if a larger number is found.
After k iterations, it returns the remaining number, representing the largest number possible after removing k digits:
3.2. Time and Space Complexity
The code iterates through k iterations in the outer loop. Inside the outer loop, there’s a while loop that iterates through the digits of num. This loop executes for each digit of the num, which is approximately log base10 ​num times since we’re dividing num by 10 in each iteration. Therefore, the time complexity of the inner loop is O(K*log10N).
We did not use any extra space, therefore the space complexity will be O(1).
4. Using Stack
In this section, we’ll see a more optimized approach to improve the complexity.
3.1. Logic
The approach involves using a stack to track the digits of the number while ensuring that the resulting number is maximized.
We’ll use the method findLargestNumberUsingStack(num, k) to implement our logic that returns the resultant number.
The function findLargestNumberUsingStack(num,k) takes two parameters: num (the original number) and k (the number of digits to remove).
Start with converting the number num into a character array or a string to iterate through its digits:
String numStr = Integer.toString(num);
int length = numStr.length();
If the number of digits to remove is the same as the length of the input number, we have to return 0:
if (k == length) return 0;
Otherwise, initialize an empty stack to store the digits:
Stack<Character> stack = new Stack<>();
Now, iterate through each digit of the number num and follow the steps:
- While the stack is not empty, the current digit is greater than the top element of the stack, and the number of remaining digits to remove (K) is greater than 0, pop elements from the stack
- Push the current digit onto the stack
for (int i = 0; i < length; i++) {
char digit = numStr.charAt(i);
while (k > 0 && !stack.isEmpty() && stack.peek() < digit) {
stack.pop();
k--;
}
stack.push(digit);
}
If there are remaining digits to remove (K), pop elements from the stack to satisfy the condition:
while (k > 0) {
stack.pop();
k--;
}
Finally, construct the largest number from the digits remaining in the stack and return the result:
while (!stack.isEmpty()) {
result.insert(0, stack.pop());
}
return Integer.parseInt(result.toString());
4.2. Time and Space Complexity
The algorithm iterates through each digit of the number once, performing constant-time operations within the loop. Therefore, the time complexity will be O(N).
The space required is primarily determined by the stack used to store the digits of the number. Therefore, the space complexity will be O(N).
5. Conclusion
In this article, we’ve examined algorithms for finding the largest number possible after removing the k digits of a number. We’ve seen how to achieve that in two ways: arithmetic and stack. We also discussed the time and space complexities of both algorithms, allowing us to choose one wisely according to our needs.
As usual, the complete code examples shown in this article are available over on GitHub.
