Build Lowest Number by Removing n digits from a given number
Given a string ‘str’ of digits and an integer ‘n’, build the lowest possible number by removing ‘n’ digits from the string and not changing the order of input digits.
Examples:
Input: str = "4325043", n = 3
Output: "2043"
Input: str = "765028321", n = 5
Output: "0221"
Input: str = "121198", n = 2
Output: "1118"
The idea is based on the fact that a character among first (n+1) characters must be there in resultant number. So we pick the smallest of first (n+1) digits and put it in result, and recur for the remaining characters. Below is complete algorithm.
Initialize result as empty string
res = ""
buildLowestNumber(str, n, res)
1) If n == 0, then there is nothing to remove.
Append the whole 'str' to 'res' and return
2) Let 'len' be length of 'str'. If 'len' is smaller or equal
to n, then everything can be removed
Append nothing to 'res' and return
3) Find the smallest character among first (n+1) characters
of 'str'. Let the index of smallest character be minIndex.
Append 'str[minIndex]' to 'res' and recur for substring after
minIndex and for n = n-minIndex
buildLowestNumber(str[minIndex+1..len-1], n-minIndex).
Below is the implementation of the above algorithm:
C++
#include <iostream> using namespace std; string buildLowestNumber(string str, int n) { // Base Case 1: If n == 0, append the whole 'str' to 'res' and return if (n == 0) { return str; } int len = str.size(); // Base Case 2: If 'len' is smaller or equal to n, everything can be removed if (len <= n) { return "" ; } // Find the smallest character among the first (n+1) characters of 'str' int minIndex = 0; for ( int i = 1; i <= n; ++i) { if (str[i] < str[minIndex]) { minIndex = i; } } // Append 'str[minIndex]' to 'res' and recur for the substring after minIndex // and for n = n-minIndex return str[minIndex] + buildLowestNumber(str.substr(minIndex + 1), n - minIndex); } int main() { string str = "765028321" ; int k = 5; string result = buildLowestNumber(str, k); // Output the result if (result.empty()) { cout << "0\n" ; } else { cout << result << "\n" ; } return 0; } |
Java
public class LowestNumber { public static String buildLowestNumber(String str, int n) { // Base Case 1: If n == 0, append the whole 'str' to 'res' and return if (n == 0 ) { return str; } int len = str.length(); // Base Case 2: If 'len' is smaller or equal to n, everything can be removed if (len <= n) { return "" ; } // Find the smallest character among the first (n+1) characters of 'str' int minIndex = 0 ; for ( int i = 1 ; i <= n; ++i) { if (str.charAt(i) < str.charAt(minIndex)) { minIndex = i; } } // Append 'str.charAt(minIndex)' to 'res' and recur for the substring after minIndex // and for n = n-minIndex return str.charAt(minIndex) + buildLowestNumber(str.substring(minIndex + 1 ), n - minIndex); } public static void main(String[] args) { String str = "765028321" ; int k = 5 ; String result = buildLowestNumber(str, k); // Output the result if (result.isEmpty()) { System.out.println( "0" ); } else { System.out.println(result); } } } |
Python3
def buildLowestNumber(s, n): # Base Case 1: If n == 0, append the whole 's' to 'res' and return if n = = 0 : return s length = len (s) # Base Case 2: If 'length' is smaller or equal to n, everything can be removed if length < = n: return "" # Find the smallest character among the first (n+1) characters of 's' min_index = 0 for i in range ( 1 , n + 1 ): if s[i] < s[min_index]: min_index = i # Append 's[min_index]' to 'res' and recur for the substring after min_index # and for n = n-min_index return s[min_index] + buildLowestNumber(s[min_index + 1 :], n - min_index) # Main function if __name__ = = "__main__" : s = "765028321" k = 5 result = buildLowestNumber(s, k) # Output the result if not result: print ( "0" ) else : print (result) |
C#
using System; class Program { static string BuildLowestNumber( string str, int n) { // Base Case 1: If n == 0, append the whole 'str' to 'res' and return if (n == 0) { return str; } int len = str.Length; // Base Case 2: If 'len' is smaller or equal to n, everything can be removed if (len <= n) { return "" ; } // Find the smallest character among the first (n+1) characters of 'str' int minIndex = 0; for ( int i = 1; i <= n; ++i) { if (str[i] < str[minIndex]) { minIndex = i; } } // Append 'str[minIndex]' to 'res' and recur for the substring after minIndex // and for n = n-minIndex return str[minIndex] + BuildLowestNumber(str.Substring(minIndex + 1), n - minIndex); } static void Main() { string str = "765028321" ; int k = 5; string result = BuildLowestNumber(str, k); // Output the result if ( string .IsNullOrEmpty(result)) { Console.WriteLine( "0" ); } else { Console.WriteLine(result); } } } |
Javascript
function buildLowestNumber(str, n) { // Base Case 1: If n == 0, append the whole 'str' to 'res' and return if (n === 0) { return str; } const len = str.length; // Base Case 2: If 'len' is smaller or equal to n, everything can be removed if (len <= n) { return "" ; } // Find the smallest character among the first (n+1) characters of 'str' let minIndex = 0; for (let i = 1; i <= n; ++i) { if (str[i] < str[minIndex]) { minIndex = i; } } // Append 'str[minIndex]' to 'res' and recur for the substring after minIndex // and for n = n-minIndex return str[minIndex] + buildLowestNumber(str.substring(minIndex + 1), n - minIndex); } // Main function const str = "765028321" ; const k = 5; const result = buildLowestNumber(str, k); // Output the result if (!result) { console.log( "0" ); } else { console.log(result); } |
221
- Time Complexity: O(N)
- Space Complexity: O(N)
Below is an optimized code in C++ contributed by Gaurav Mamgain
C++14
// C++ program to build the smallest number by removing // n digits from a given number #include <bits/stdc++.h> using namespace std; void insertInNonDecOrder(deque< char >& dq, char ch) { // If container is empty , insert the current digit if (dq.empty()) dq.push_back(ch); else { char temp = dq.back(); // Keep removing digits larger than current digit // from the back side of deque while (temp > ch && !dq.empty()) { dq.pop_back(); if (!dq.empty()) temp = dq.back(); } // Insert the current digit dq.push_back(ch); } return ; } string buildLowestNumber(string str, int n) { int len = str.length(); // Deleting n digits means we need to print k digits int k = len - n; deque< char > dq; string res = "" ; // Leaving rightmost k-1 digits we need to choose // minimum digit from rest of the string and print it int i; for (i = 0; i <= len - k; i++) // Insert new digit from the back side in // appropriate position and/ keep removing // digits larger than current digit insertInNonDecOrder(dq, str[i]); // Now the minimum digit is at front of deque while (i < len) { // keep the minimum digit in output string res += dq.front(); // remove minimum digit dq.pop_front(); // Again insert new digit from the back // side in appropriate position and keep // removing digits larger than current digit insertInNonDecOrder(dq, str[i]); i++; } // Now only one element will be there in the deque res += dq.front(); dq.pop_front(); return res; } string lowestNumber(string str, int n) { string res = buildLowestNumber(str, n); // Remove all the leading zeroes string ans = "" ; int flag = 0; for ( int i = 0; i < res.length(); i++) { if (res[i] != '0' || flag == 1) { flag = 1; ans += res[i]; } } if (ans.length() == 0) return "0" ; else return ans; } // Driver program to test above function int main() { string str = "765028321" ; int n = 5; cout <<lowestNumber(str, n) << endl; return 0; } // This code is contributed by Gaurav Mamgain |
Java
// Java program to build the smallest number by removing // n digits from a given number import java.util.*; class GFG { static void insertInNonDecOrder(Deque<Character> dq, char ch) { // If container is empty , insert the current digit if (dq.isEmpty()) dq.addLast(ch); else { char temp = dq.peekLast(); // Keep removing digits larger than current // digit from the back side of deque while (temp > ch && !dq.isEmpty()) { dq.pollLast(); if (!dq.isEmpty()) temp = dq.peekLast(); } // Insert the current digit dq.addLast(ch); } return ; } static String buildLowestNumber(String str, int n) { int len = str.length(); // Deleting n digits means we need to print k digits int k = len - n; Deque<Character> dq = new ArrayDeque<>(); String res = "" ; // Leaving rightmost k-1 digits we need to choose // minimum digit from rest of the string and print // it int i; for (i = 0 ; i <= len - k; i++) // Insert new digit from the back side in // appropriate position and/ keep removing // digits larger than current digit insertInNonDecOrder(dq, str.charAt(i)); // Now the minimum digit is at front of deque while (i < len) { // keep the minimum digit in output string res += dq.peekFirst(); // remove minimum digit dq.pollFirst(); // Again insert new digit from the back // side in appropriate position and keep // removing digits larger than current digit insertInNonDecOrder(dq, str.charAt(i)); i++; } // Now only one element will be there in the deque res += dq.peekFirst(); dq.pollFirst(); return res; } static String lowestNumber(String str, int n) { String res = buildLowestNumber(str, n); // Remove all the leading zeroes String ans = "" ; int flag = 0 ; for ( int i = 0 ; i < res.length(); i++) { if (res.charAt(i) != '0' || flag == 1 ) { flag = 1 ; ans += res.charAt(i); } } if (ans.length() == 0 ) return "0" ; else return ans; } // Driver Code public static void main(String[] args) { String str = "765028321" ; int n = 5 ; System.out.println(lowestNumber(str, n)); } } // This code is contributed by Karandeep1234 |
Python3
# Python program to build the smallest number by removing # n digits from a given number def insertInNonDecOrder(dq, ch): # If container is empty , insert the current digit if len (dq) = = 0 : dq.append(ch) else : temp = dq[ len (dq) - 1 ] # Keep removing digits larger than current digit # from the back side of deque while (temp > ch and len (dq) > 0 ): dq.pop( len (dq) - 1 ) if ( len (dq) > 0 ): temp = dq[ len (dq) - 1 ] # Insert the current digit dq.append(ch) return def buildLowestNumber( str , n): length = len ( str ) # Deleting n digits means we need to print k digits k = length - n dq = [] res = "" # Leaving rightmost k-1 digits we need to choose # minimum digit from rest of the string and print it i = 0 for i in range (length - k + 1 ): # Insert new digit from the back side in # appropriate position and/ keep removing # digits larger than current digit insertInNonDecOrder(dq, str [i]) i = i + 1 # Now the minimum digit is at front of deque while (i < length): # keep the minimum digit in output string res = res + dq[ 0 ] # remove minimum digit dq.pop( 0 ) # Again insert new digit from the back # side in appropriate position and keep # removing digits larger than current digit insertInNonDecOrder(dq, str [i]) i = i + 1 # Now only one element will be there in the deque res = res + dq[ 0 ] dq.pop( 0 ) return res def lowestNumber( str , n): res = buildLowestNumber( str , n) # Remove all the leading zeroes ans = "" flag = 0 for i in range ( len (res)): if res[i] ! = '0' or flag = = 1 : flag = 1 ans + = res[i] if len (ans) = = 0 : return "0" else : return ans # Driver program to test above function str = "765028321" n = 5 print (lowestNumber( str , n)) # This code is contributed by Arushi Goel. |
C#
// C# program to build the smallest number by removing // n digits from a given number using System; using System.Collections.Generic; class GFG { static void insertInNonDecOrder( ref LinkedList< char > dq, char ch) { // If container is empty , insert the current digit if (dq.Count == 0) dq.AddLast(ch); else { char temp = dq.Last.Value; // Keep removing digits larger than current // digit from the back side of deque while (temp > ch && dq.Count > 0) { dq.RemoveLast(); if (dq.Count > 0) temp = dq.Last.Value; } // Insert the current digit dq.AddLast(ch); } return ; } static string buildLowestNumber( string str, int n) { int len = str.Length; // Deleting n digits means we need to print k digits int k = len - n; LinkedList< char > dq = new LinkedList< char >(); string res = "" ; // Leaving rightmost k-1 digits we need to choose // minimum digit from rest of the string and print // it int i; for (i = 0; i <= len - k; i++) // Insert new digit from the back side in // appropriate position and/ keep removing // digits larger than current digit insertInNonDecOrder( ref dq, str[i]); // Now the minimum digit is at front of deque while (i < len) { // keep the minimum digit in output string res += dq.First.Value; // remove minimum digit dq.RemoveFirst(); // Again insert new digit from the back // side in appropriate position and keep // removing digits larger than current digit insertInNonDecOrder( ref dq, str[i]); i++; } // Now only one element will be there in the deque res += dq.First.Value; dq.RemoveFirst(); return res; } static string lowestNumber( string str, int n) { string res = buildLowestNumber(str, n); // Remove all the leading zeroes string ans = "" ; int flag = 0; for ( int i = 0; i < res.Length; i++) { if (res[i] != '0' || flag == 1) { flag = 1; ans += res[i]; } } if (ans.Length == 0) return "0" ; else return ans; } // Driver program to test above function public static void Main() { string str = "765028321" ; int n = 5; Console.WriteLine(lowestNumber(str, n)); } } |
Javascript
// javascript program to build the smallest number by removing // n digits from a given number function insertInNonDecOrder(dq, ch) { // If container is empty , insert the current digit if (dq.length == 0) dq.push(ch); else { let temp = dq[dq.length - 1]; // Keep removing digits larger than current digit // from the back side of deque while (temp > ch && dq.length > 0) { dq.pop(); if (dq.length > 0) temp = dq[dq.length - 1]; } // Insert the current digit dq.push(ch); } return ; } function buildLowestNumber(str, n) { let len = str.length; // Deleting n digits means we need to print k digits let k = len - n; let dq = []; let res = "" ; // Leaving rightmost k-1 digits we need to choose // minimum digit from rest of the string and print it let i = 0; for (i = 0; i <= len - k; i++) // Insert new digit from the back side in // appropriate position and/ keep removing // digits larger than current digit insertInNonDecOrder(dq, str[i]); // Now the minimum digit is at front of deque while (i < len) { // keep the minimum digit in output string res = res + dq[0]; // remove minimum digit dq.shift(); // Again insert new digit from the back // side in appropriate position and keep // removing digits larger than current digit insertInNonDecOrder(dq, str[i]); i = i + 1; } // Now only one element will be there in the deque res = res + dq[0]; dq.shift(); return res; } function lowestNumber(str, n) { let res = buildLowestNumber(str, n); // Remove all the leading zeroes let ans = "" ; let flag = 0; for (let i = 0; i < res.length; i++) { if (res[i] != '0' || flag == 1) { flag = 1; ans += res[i]; } } if (ans.length == 0) return "0" ; else return ans; } // Driver program to test above function let str = "765028321" ; let n = 5; console.log(lowestNumber(str, n)); // This code is contributed by Nidhi Goel. |
221
Time Complexity: O(N)
Space Complexity: O(N)
Approach-2:
Let’s suppose the length of the given string num be n.so the result string will contain the length of n-k.
As we proceed to solve this problem we should make sure that the output string contains minimum values at their high weightage positions. so we ensure that by using a stack.
- Return 0 if k >=n. and return num if k=0.
- Create a stack and iterate through num string and push the value at that position if it is greater than the top element of the stack.
- Iterate through the num string and if the integer value at that position is less than the top of the stack we will pop the stack and decrement k until we reach the condition where the top of the stack is less than the value we are looking at(while k>0) (by this we are making sure that most significant positions of the result are filled with minimum values).
- If the k is still greater than 0 we will pop stack until k becomes 0.
- Append the elements in the stack to the result string.
- Delete leading zeroes from the result string.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; string removeKdigits(string num, int k) { int n = num.size(); stack< char > mystack; // Store the final string in stack for ( char c : num) { while (!mystack.empty() && k > 0 && mystack.top() > c) { mystack.pop(); k -= 1; } if (!mystack.empty() || c != '0' ) mystack.push(c); } // Now remove the largest values from the top of the // stack while (!mystack.empty() && k--) mystack.pop(); if (mystack.empty()) return "0" ; // Now retrieve the number from stack into a string // (reusing num) while (!mystack.empty()) { num[n - 1] = mystack.top(); mystack.pop(); n -= 1; } return num.substr(n); } int main() { string str = "765028321" ; int k = 5; cout << removeKdigits(str, k); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { public static String removeKdigits(String num, int k) { StringBuilder result = new StringBuilder(); // We have to delete all digits if (k >= num.length()) { return "0" ; } // Nothing to delete if (k == 0 ) { return num; } Stack<Character> s = new Stack<Character>(); for ( int i = 0 ; i < num.length(); i++) { char c = num.charAt(i); // Removing all digits in stack that are greater // than this digit(since they have higher // weightage) while (!s.isEmpty() && k > 0 && s.peek() > c) { s.pop(); k--; } // ignore pushing 0 if (!s.isEmpty() || c != '0' ) s.push(c); } // If our k isnt 0 yet then we keep popping out the // stack until k becomes 0 while (!s.isEmpty() && k > 0 ) { k--; s.pop(); } if (s.isEmpty()) return "0" ; while (!s.isEmpty()) { result.append(s.pop()); } String str = result.reverse().toString(); return str; } // Driver Code public static void main(String[] args) { String s = "765028321" ; int k = 5 ; System.out.println(removeKdigits(s, 5 )); } } // this code is contributed by gireeshgudaparthi |
Python3
# Python program for the above approach def removeKdigits(num, k): n = len (num) mystack = [] # Store the final string in stack for c in num: while ( len (mystack) > 0 and k > 0 and mystack[ - 1 ] > c): mystack.pop() k - = 1 if ( len (mystack) > 0 or c ! = '0' ): mystack.append(c) # Now remove the largest values from the top of the # stack while ( len (mystack) > 0 and k): k - = 1 mystack.pop() if ( len (mystack) = = 0 ): return "0" # Now retrieve the number from stack into a string # (reusing num) num = list (num) while ( len (mystack) > 0 ): num[n - 1 ] = mystack[ - 1 ] mystack.pop() n - = 1 return "".join(num[n:]) # driver code Str = "765028321" k = 5 print (removeKdigits( Str , k)) # This code is contributed by shinjanpatra |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { public static string removeKdigits( string Num, int k){ char [] num = Num.ToCharArray(); int n = num.Length; Stack< char > mystack = new Stack< char >(); // Store the final string in stack for ( int i = 0; i < num.Length; i++) { while (mystack.Count > 0 && k > 0 && mystack.Peek() > num[i]) { mystack.Pop(); k = k - 1; } if (mystack.Count > 0 || num[i] != '0' ) mystack.Push(num[i]); } // Now remove the largest values from the top of the // stack while (mystack.Count > 0 && k > 0) { mystack.Pop(); k = k - 1; } if (mystack.Count == 0) return "0" ; // Now retrieve the number from stack into a string // (reusing num) while (mystack.Count > 0) { char temp = mystack.Peek(); num[n - 1] = temp; mystack.Pop(); n = n - 1; } return new string (num).Substring(n); } public static void Main(){ string str = "765028321" ; int k = 5; Console.WriteLine(removeKdigits(str, k)); } } // THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
Javascript
<script> // JavaScript program for the above approach function removeKdigits(num,k){ let n = num.length let mystack = [] // Store the final string in stack for (let c of num){ while (mystack.length>0 && k > 0 && mystack[mystack.length - 1] > c){ mystack.pop() k -= 1 } if (mystack.length>0 || c != '0' ) mystack.push(c) } // Now remove the largest values from the top of the // stack while (mystack.length>0 && k){ k -= 1 mystack.pop() } if (mystack.length == 0) return "0" // Now retrieve the number from stack into a string // (reusing num) while (mystack.length>0){ num = num.replace(num[n - 1] , mystack[mystack.length-1]) mystack.pop() n -= 1 } return num.substring(n,) } // driver code let Str = "765028321" let k = 5 document.write(removeKdigits(Str, k)) // code is contributed by shinjanpatra </script> |
221
Time complexity: O(N)
Space complexity: O(N)
Contact Us