Largest number not exceeding N that does not contain any of the digits of S

0 0 11 minutes read

Given a numberic string N (1 ≤ |N| ≤ 10⁵) and another numeric string S (1 ≤ |S| ≤ 10⁵), 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 S
string 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 Code
int 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 approach
import 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 approach
 
def 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 S
def 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 Code
if __name__ == "__main__":
    N = "12345"
    S = "23"
  
    print(greatestReducedNumber(N, S))

C#

// C# program to implement
// the above approach
 
using 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 s
function 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 S
function 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 Code
let N = "12345";
let S = "23";
 
console.log(greatestReducedNumber(N, S)); // Output: 11999

Output

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 idx^th 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 S
string 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 Code
int main()
{
    string N = "12345";
    string S = "23";
 
    cout << greatestReducedNumber(N, S);
 
    return 0;
}

Java

// Java program to implement
// the above approach
 
import 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 S
def 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 code
N = "12345"
S = "23"
 
print(greatestReducedNumber(N, S))
 
# This code is contributed by divyeshrabadiya07.

C#

// C# program to implement
// the above approach
using 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 S
function 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 Code
let N = "12345";
let S = "23";
document.write( greatestReducedNumber(N, S));
 
// This code is contributed by rohitsingh07052
</script>

Output

Time complexity: O(|N| + |s|)
Auxiliary space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!