Find Largest Number If To Remove k Digits From It

Yatin BatraMay 10th, 2024Last Updated: May 10th, 2024

0 196 3 minutes read

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:

1	`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:

1	`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.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

I agree to the Terms and Privacy Policy

Find Largest Number If To Remove k Digits From It