A common problem in programming arises when you need to find the largest possible number by removing k digits from a given number. Let us delve into Java’s method to find the largest number if to remove k digits from a source number.

1. Using the Arithmetic approach

Below is the code snippet to find the largest number possible after removing k digits from a given number using arithmetic operations.

package com.jcg.example;

public class LargestNumberAfterRemovingKDigits {
 
 public static String removeKDigits(String num, int k) {
 // Base case: If the number of digits to be removed is equal to the length of the number, return "0".
 if (k == num.length()) {
 return "0";
 }
 
 StringBuilder result = new StringBuilder();
 int n = num.length();
 int keep = n - k; // Number of digits to keep
 
 // Greedy algorithm to find the largest number
 for (char digit : num.toCharArray()) {
 while (k > 0 && result.length() > 0 && result.charAt(result.length() - 1) < digit) {
 result.deleteCharAt(result.length() - 1);
 k--;
 }
 result.append(digit);
 }
 
 // Remove extra digits if k > 0
 result.setLength(keep);
 
 // Remove leading zeros
 int startIndex = 0;
 while (startIndex < result.length() - 1 && result.charAt(startIndex) == '0') {
 startIndex++;
 }
 
 return result.substring(startIndex);
 }

 public static void main(String[] args) {
 String num = "1432219";
 int k = 3;
 String largestNumber = removeKDigits(num, k);
 System.out.println("Largest number after removing " + k + " digits: " + largestNumber);
 }
}

1.1 Code Breakdown

• removeKDigits Method:
  • The method takes a string representation of a number and an integer k representing the number of digits to remove.
  • A base case checks if k is equal to the length of the number, in which case “0” is returned.
  • We initialize a StringBuilder to store the result and calculate the number of digits to keep.
  • A greedy algorithm iterates through each digit of the number, removing digits until we’ve removed k digits or the last digit is smaller than the current digit.
  • After the loop, any remaining digits to remove are removed from the end of the result.
  • Leading zeros are removed from the result before returning it.
• Main Method:
  • The main method demonstrates the usage of the removeKDigits method with a sample input.

1.2 Output

The output of the provided Java code will be:

Largest number after removing 3 digits: 4329

2. Using the Stack approach

Below is the code snippet to find the largest number possible after removing k digits from a given number using stack operations.

package com.jcg.example;

import java.util.Stack;

public class LargestNumberAfterRemovingKDigits {

 public static String removeKDigits(String num, int k) {
 Stack<Character> stack = new Stack<>();
 
 // Remove digits from the number
 for (char digit : num.toCharArray()) {
 while (k > 0 && !stack.isEmpty() && stack.peek() < digit) {
 stack.pop();
 k--;
 }
 stack.push(digit);
 }
 
 // Remove remaining digits if k > 0
 while (k > 0) {
 stack.pop();
 k--;
 }
 
 // Construct the result string
 StringBuilder result = new StringBuilder();
 while (!stack.isEmpty()) {
 result.insert(0, stack.pop());
 }
 
 // Remove leading zeros
 int startIndex = 0;
 while (startIndex < result.length() - 1 && result.charAt(startIndex) == '0') {
 startIndex++;
 }
 
 return result.substring(startIndex);
 }

 public static void main(String[] args) {
 String num = "1432219";
 int k = 3;
 String largestNumber = removeKDigits(num, k);
 System.out.println("Largest number after removing " + k + " digits: " + largestNumber);
 }
}

2.1 Code Breakdown

• removeKDigits Method:
  • The method takes a string representation of a number and an integer k representing the number of digits to remove.
  • We initialize a stack to store digits.
  • We iterate through each digit of the number and use a stack to remove digits while maintaining the highest possible number.
  • The remaining digits are removed if k is greater than 0.
  • The result string is constructed by popping digits from the stack.
  • Leading zeros are removed from the result before returning it.
• Main Method:
  • The main method demonstrates the usage of the removeKDigits method with a sample input.

2.2 Output

The output of the provided Java code will be:

Largest number after removing 3 digits: 4329

3. Conclusion

The code adeptly determines the largest number attainable by selectively removing k digits from a given number through arithmetic operations, showcasing its efficiency in optimizing the output. Additionally, it employs a stack data structure to achieve the same objective, highlighting its versatility in handling different approaches to the problem.