Given a numberic string N (1 ≤ |N| ≤ 105) and another numeric string S (1 ≤ |S| ≤ 105), the task is to find the maximum number ≤ N such that it doesn’t contain digits of string S. Remove leading zeros, if required.
Note: The string S doesn’t contain ‘0’.
Examples:
Input: N = “2004”, S = “2”
Output: 1999
Explanation:
2004 has digit 2 which is in the string S.
Therefore, keep reducing it by 1 until the number obtained does not contain 2.
Therefore, the largest number that can be obtained is 1999.Input: N = “12345”, S = “23”
Output: 11999
Naive Approach: For every value of N, check if it contains any of the digits of S. Keep reducing N by 1 until any digit that is present in S does not occur in N.
Implementation:-
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;bool NotPresent(int i,string s){ //getting integer value of s int temp = stoi(s); //chacking for each digit of i present in s or not //if present any then return false //else return true while(i) { int digit = i%10; i/=10; //taking temp into t so that we will not lost temp int t = temp; while(t) { int digit2 = t%10; t/=10; //if found any digit present if(digit2==digit)return false; } } return true;}// Function to obtain the largest number not exceeding// num which does not contain any digits present in Sstring greatestReducedNumber(string num, string s){ //changing string to integer int N = stoi(num); for(int i=N;i>=1;i--) { if(NotPresent(i,s)){ return to_string(i); } } return "-1";}// Driver Codeint main(){ string N = "12345"; string S = "23"; cout << greatestReducedNumber(N, S); return 0;}//This code is contributed by shubhamrajput6156 |
Java
// Java program to implement// the above approachimport java.util.*;class GFG { // Function to check the presence // of any digit of i in s or not static boolean NotPresent(int i, String s) { // getting integer value of s int temp = Integer.parseInt(s); // checking for each digit of i // present in s or not while (i != 0) { int digit = i % 10; i /= 10; // taking temp into t so that // we will not lost temp int t = temp; while (t != 0) { int digit2 = t % 10; t /= 10; // if found any digit present if (digit2 == digit) return false; } } return true; } // Function to obtain the largest number // not exceeding num which does not contain // any digits present in S static String greatestReducedNumber(String num, String s) { // changing string to integer int N = Integer.parseInt(num); for (int i = N; i >= 1; i--) { if (NotPresent(i, s)) { return Integer.toString(i); } } return "-1"; } // Driver Code public static void main(String[] args) { String N = "12345"; String S = "23"; System.out.println(greatestReducedNumber(N, S)); }} |
Python3
# C++ program to implement# the above approachdef NotPresent(i, s): #getting integer value of s temp = int(s) #checking for each digit of i present in s or not #if present any then return false #else return true while i: digit = i % 10 i = i // 10 #taking temp into t so that we will not lose temp t = temp while t: digit2 = t % 10 t = t // 10 #if found any digit present if digit2 == digit: return False return True# Function to obtain the largest number not exceeding# num which does not contain any digits present in Sdef greatestReducedNumber(num, s): #changing string to integer N = int(num) for i in range(N, 0, -1): if NotPresent(i, s): return str(i) return "-1" # Driver Codeif __name__ == "__main__": N = "12345" S = "23" print(greatestReducedNumber(N, S)) |
C#
// C# program to implement// the above approachusing System;class GFG{ static bool NotPresent(int i, string s) { //getting integer value of s int temp = int.Parse(s); //checking for each digit of i present in s or not //if present any then return false //else return true while (i != 0) { int digit = i % 10; i /= 10; //taking temp into t so that we will not lost temp int t = temp; while (t != 0) { int digit2 = t % 10; t /= 10; //if found any digit present if (digit2 == digit) return false; } } return true; } // Function to obtain the largest number not exceeding // num which does not contain any digits present in S static string GreatestReducedNumber(string num, string s) { //changing string to integer int N = int.Parse(num); for (int i = N; i >= 1; i--) { if (NotPresent(i, s)) { return i.ToString(); } } return "-1"; } // Driver code static void Main(string[] args) { string N = "12345"; string S = "23"; Console.WriteLine(GreatestReducedNumber(N, S)); }}// This code is contributed by bhardwajji |
Javascript
// Function to check if i is not present in sfunction NotPresent(i, s) { // Converting s to integer let temp = parseInt(s); // Checking for each digit of i present in s or not // If any digit is present, then return false // Else, return true while (i) { let digit = i % 10; i = Math.floor(i / 10); // Taking temp into t so that we will not lose temp let t = temp; while (t) { let digit2 = t % 10; t = Math.floor(t / 10); // If found any digit present if (digit2 == digit) { return false; } } } return true;}// Function to obtain the largest number not exceeding num// which does not contain any digits present in Sfunction greatestReducedNumber(num, s) { // Converting num to integer let N = parseInt(num); for (let i = N; i > 0; i--) { if (NotPresent(i, s)) { return i.toString(); } } return "-1";}// Driver Codelet N = "12345";let S = "23";console.log(greatestReducedNumber(N, S)); // Output: 11999 |
Output
11999
Time Complexity: O(|N| * log(|N|) * |S|)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using Hashing. Follow the steps below to solve the problem:
- Iterate over the characters of the string S and store the distinct characters of S in a Map.
- Traverse the string N.
- If any digit of N is found to be present in S, say idxth digit, reduce N[idx] to the largest digit not present in S, say LargestDig.
- Digits in range [idx + 1, |N| – 1] are changed to LargestDig.
Illustration:
Consider N = “2004” and S = “2”.
To remove 2, it is changed to 1 and the remaining digits are changed to the largest digit which is not present in S, that is digit 9.
- Remove all the leading zeros from the number.
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 obtain the largest number not exceeding// num which does not contain any digits present in Sstring greatestReducedNumber(string num, string s){ // Stores digits of S vector<bool> vis_s(10, false); // Traverse the string S for (int i = 0; i < (int)s.size(); i++) { // Set occurrence as true vis_s[int(s[i]) - 48] = true; } int n = num.size(); int in = -1; // Traverse the string n for (int i = 0; i < n; i++) { if (vis_s[(int)num[i] - '0']) { in = i; break; } } // All digits of num are not // present in string s if (in == -1) { return num; } for (char dig = num[in]; dig >= '0'; dig--) { if (vis_s[(int)dig - '0'] == 0) { num[in] = dig; break; } } char LargestDig = '0'; for (char dig = '9'; dig >= '0'; dig--) { if (vis_s[dig - '0'] == false) { // Largest Digit not present // in the string s LargestDig = dig; break; } } // Set all digits from positions // in + 1 to n - 1 as LargestDig for (int i = in + 1; i < n; i++) { num[i] = LargestDig; } // Counting leading zeroes int Count = 0; for (int i = 0; i < n; i++) { if (num[i] == '0') Count++; else break; } // Removing leading zeroes num.erase(0, Count); // If the string becomes null if ((int)num.size() == 0) return "0"; // Return the largest number return num;}// Driver Codeint main(){ string N = "12345"; string S = "23"; cout << greatestReducedNumber(N, S); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.Arrays;class GFG { // Function to obtain the largest number not exceeding // num which does not contain any digits present in S static String greatestReducedNumber(String num, String s) { // Stores digits of S Boolean[] vis_s = new Boolean[10]; Arrays.fill(vis_s, Boolean.FALSE); // Traverse the string S for (int i = 0; i < (int)s.length(); i++) { // Set occurrence as true vis_s[(int)(s.charAt(i)) - 48] = true; } int n = num.length(); int in = -1; // Traverse the string n for (int i = 0; i < n; i++) { if (vis_s[(int)num.charAt(i) - '0']) { in = i; break; } } // All digits of num are not // present in string s if (in == -1) { return num; } for (char dig = num.charAt(in); dig >= '0'; dig--) { if (vis_s[(int)dig - '0'] == false) { num = num.substring(0, in) + dig + num.substring(in + 1, n); break; } } char LargestDig = '0'; for (char dig = '9'; dig >= '0'; dig--) { if (vis_s[dig - '0'] == false) { // Largest Digit not present // in the string s LargestDig = dig; break; } } // Set all digits from positions // in + 1 to n - 1 as LargestDig for (int i = in + 1; i < n; i++) { num = num.substring(0, i) + LargestDig; } // Counting leading zeroes int Count = 0; for (int i = 0; i < n; i++) { if (num.charAt(i) == '0') Count++; else break; } // Removing leading zeroes num = num.substring(Count, n); // If the string becomes null if ((int)num.length() == 0) return "0"; // Return the largest number return num; } // Driver Code public static void main(String[] args) { String N = "12345"; String S = "23"; System.out.print(greatestReducedNumber(N, S)); }}// This code is contributed by subhammahato348 |
Python3
# Python3 program to implement# the above approach# Function to obtain the largest number not exceeding# num which does not contain any digits present in Sdef greatestReducedNumber(num, s) : # Stores digits of S vis_s = [False] * 10 # Traverse the string S for i in range(len(s)) : # Set occurrence as true vis_s[(ord)(s[i]) - 48] = True n = len(num) In = -1 # Traverse the string n for i in range(n) : if (vis_s[ord(num[i]) - ord('0')]) : In = i break # All digits of num are not # present in string s if (In == -1) : return num for dig in range(ord(num[In]), ord('0') - 1, -1) : if (vis_s[dig - ord('0')] == False) : num = num[0 : In] + chr(dig) + num[In + 1 : n - In - 1] break LargestDig = '0' for dig in range(ord('9'), ord('0') - 1, -1) : if (vis_s[dig - ord('0')] == False) : # Largest Digit not present # in the string s LargestDig = dig break # Set all digits from positions # in + 1 to n - 1 as LargestDig for i in range(In + 1, n) : num = num[0 : i] + chr(LargestDig) # Counting leading zeroes Count = 0 for i in range(n) : if (num[i] == '0') : Count += 1 else : break # Removing leading zeroes num = num[Count : n] # If the string becomes null if (int(len(num)) == 0) : return "0" # Return the largest number return num # Driver codeN = "12345"S = "23"print(greatestReducedNumber(N, S))# This code is contributed by divyeshrabadiya07. |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic; class GFG { // Function to obtain the largest number not exceeding // num which does not contain any digits present in S static string greatestReducedNumber(string num, string s) { // Stores digits of S bool[] vis_s = new bool[10]; // Traverse the string S for (int i = 0; i < (int)s.Length; i++) { // Set occurrence as true vis_s[(int)(s[i]) - 48] = true; } int n = num.Length; int In = -1; // Traverse the string n for (int i = 0; i < n; i++) { if (vis_s[(int)num[i] - '0']) { In = i; break; } } // All digits of num are not // present in string s if (In == -1) { return num; } for (char dig = num[In]; dig >= '0'; dig--) { if (vis_s[(int)dig - '0'] == false) { num = num.Substring(0, In) + dig + num.Substring(In + 1, n - In - 1); break; } } char LargestDig = '0'; for (char dig = '9'; dig >= '0'; dig--) { if (vis_s[dig - '0'] == false) { // Largest Digit not present // in the string s LargestDig = dig; break; } } // Set all digits from positions // in + 1 to n - 1 as LargestDig for (int i = In + 1; i < n; i++) { num = num.Substring(0, i) + LargestDig; } // Counting leading zeroes int Count = 0; for (int i = 0; i < n; i++) { if (num[i] == '0') Count++; else break; } // Removing leading zeroes num = num.Substring(Count, n); // If the string becomes null if ((int)num.Length == 0) return "0"; // Return the largest number return num; } // Driver code static void Main() { string N = "12345"; string S = "23"; Console.Write(greatestReducedNumber(N, S)); }}// This code is contributed by divyesh072019 |
Javascript
<script>// JavaScript program to implement// the above approach// Function to obtain the largest number not exceeding// num which does not contain any digits present in Sfunction greatestReducedNumber( num, s){ // Stores digits of S let vis_s = [false,false,false,false,false,false,false,false,false,false]; // Traverse the string S for (let i = 0; i < s.length; i++) { // Set occurrence as true vis_s[Number(s[i]) - 48] = true; } let n = num.length; let inn = -1; // Traverse the string n for (let i = 0; i < n; i++) { if (vis_s[Number(num[i]) - '0']) { inn = i; break; } } // All digits of num are not // present in string s if (inn == -1) { return num; } for (let dig = String(num[inn]); dig >= '0'; dig--) { if (vis_s[Number(dig) - '0'] == 0) { num[inn] = dig; break; } } let LargestDig = '0'; for (let dig = '9'; dig >= '0'; dig--) { if (vis_s[dig - '0'] == false) { // Largest Digit not present // in the string s LargestDig = dig; break; } } // Set all digits from positions // in + 1 to n - 1 as LargestDig for (let i = inn + 1; i < n; i++) { num[i] = LargestDig; } // Counting leading zeroes let Count = 0; for (let i = 0; i < n; i++) { if (num[i] == '0') Count++; else break; } // Removing leading zeroes num = Number(num).toString(); // If the string becomes null if (num.length == 0) return "0"; // Return the largest number return num;}// Driver Codelet N = "12345";let S = "23";document.write( greatestReducedNumber(N, S));// This code is contributed by rohitsingh07052</script> |
Output
11999
Time complexity: O(|N| + |s|)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
