Largest number possible after removal of K digits
Given a positive number N, the target is to find the largest number that can be formed after removing any K digits from N.
Examples:
Input: N = 6358, K = 1
Output: 658
Input: N = 2589, K = 2
Output: 89
Approach:
- Iterate a loop K times.
- During every iteration, remove every digit from the current value of N once and store the maximum of all the numbers obtained.
- In order to achieve this, we store the maximum of (N / (i * 10)) * i + (N % i) where i ranges from [1, 10l – 1] where l denotes the number of digits of the current value of N.
- Consider this maximum as the current value of N and proceed to the next iteration and repeat the above step.
- Thus, after every iteration, we have the least digit from the current value of N removed. On repeating the process K times, we obtain the largest number possible.
For example:
Let us analyze this approach for N = 6358, K = 1
The different possibilities after removal of every digit once are as follows:
(6358 / 10) * 1 + 6358 % 1 = 635 + 0 = 635
(6358 / 100) * 10 + 6358 % 10 = 630 + 8 = 638
(6358 / 1000) * 100 + 6358 % 100 = 600 + 58 = 658
(6358 / 10000) * 1000 + 6358 % 1000 = 0 + 358 = 358
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to return the // largest number possible int maxnumber( int n, int k) { // Generate the largest number // after removal of the least // K digits one by one for ( int j = 0; j < k; j++) { int ans = 0; int i = 1; // Remove the least digit // after every iteration while (n / i > 0) { // Store the numbers formed after // removing every digit once int temp = (n / (i * 10)) * i + (n % i); i *= 10; // Compare and store the maximum ans = max(ans, temp); } // Store the largest // number remaining n = ans; } // Return the remaining number // after K removals return n; } // Driver code int main() { int n = 6358; int k = 1; cout << maxnumber(n, k) << endl; return 0; } |
Java
// Java program to implement // the above approach import java.util.*; import java.math.*; class GFG { // Function to return the // largest number possible static int maxnumber( int n, int k) { // Generate the largest number // after removal of the least // K digits one by one for ( int j = 0 ; j < k; j++) { int ans = 0 ; int i = 1 ; // Remove the least digit // after every iteration while (n / i > 0 ) { // Store the numbers formed after // removing every digit once int temp = (n / (i * 10 )) * i + (n % i); i *= 10 ; // Compare and store the maximum ans = Math.max(ans, temp); } n = ans; } // Return the remaining number // after K removals return n; } // Driver code public static void main(String[] args) { int n = 6358 ; int k = 1 ; System.out.println(maxnumber(n, k)); } } |
Python3
# Python program to implement # the above approach def maxnumber(n, k): # Function to return the # largest number possible for i in range ( 0 , k): # Generate the largest number # after removal of the least K digits # one by one ans = 0 i = 1 while n / / i > 0 : # Remove the least digit # after every iteration temp = (n / / (i * 10 )) * i + (n % i) i * = 10 # Store the numbers formed after # removing every digit once # Compare and store the maximum if temp > ans: ans = temp n = ans # Return the remaining number # after K removals return ans; n = 6358 k = 1 print (maxnumber(n, k)) |
C#
// C# program to implement // the above approach using System; class GFG { // Function to return the // largest number possible static int maxnumber( int n, int k) { // Generate the largest number // after removal of the least // K digits one by one for ( int j = 0; j < k; j++) { int ans = 0; int i = 1; // Remove the least digit // after every iteration while (n / i > 0) { // Store the numbers formed after // removing every digit once int temp = (n / (i * 10)) * i + (n % i); i *= 10; // Compare and store the maximum if (temp > ans) ans = temp; } // Store the largest // number remaining n = ans; } // Return the remaining number // after K removals return n; } // Driver code static public void Main() { int n = 6358; int k = 1; Console.WriteLine(maxnumber(n, k)); } } |
Javascript
<script> // Javascript program to implement // the above approach // Function to return the // largest number possible function maxnumber(n, k) { // Generate the largest number // after removal of the least // K digits one by one for ( var j = 0; j < k; j++) { var ans = 0; var i = 1; // Remove the least digit // after every iteration while (parseInt(n / i) > 0) { // Store the numbers formed after // removing every digit once var temp = parseInt(n / (i * 10)) * i + (n % i); i *= 10; // Compare and store the maximum ans = Math.max(ans, temp); } // Store the largest // number remaining n = ans; } // Return the remaining number // after K removals return n; } // Driver code var n = 6358; var k = 1; document.write( maxnumber(n, k)); </script> |
Output:
658
Time Complexity: O(K*log10N)
Auxiliary Space: O(1)
Contact Us