Largest possible number by deleting given digit

0 0 5 minutes read

Find the largest positive integer that can be formed by deleting only one occurrence of a given digit.

Examples:

Input: num = 56321, digit = 5
Output: 6321
Explanation: Since the number 56321 contain only 1 occurrence of 5, we can remove it to get 6321 which is the largest possible positive number.

Input: num = 936230, digit = 3
Output: 96230
Explanation: Since the number 936230 contain 2 occurrences of 3, we can remove either 1st occurrence to get 96230 or remove 2nd occurrence to get 93620. Among the both, 96230 is the largest possible positive number.

Approach: The problem can be solved based on the following idea:

To find the maximum number, delete an occurrence in such a position where the next digit is greater than it. Because then the number formed will be large. Such a position should be as close to left as possible for higher values.

Follow the steps mentioned below to implement the idea:

Remove the leftmost occurrence of X if it’s followed by a larger digit.
If no occurrence of X is followed by a digit greater than X then remove the last occurrence of the digit.

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>
using namespace std;
 
string removeX(string N, char X)
{
   
    // Stores the index of X
    // that has to be removed
    int index = -1;
 
    // Find leftmost occurrence of X
    // such that the digit just after X
    // is greater than X
    for (int i = 0; i < N.length() - 1; i++) {
        if (N[i] == X && N[i] - '0' < N[i + 1] - '0') {
 
            // Update index and break
            index = i;
            break;
        }
    }
 
    // If no occurrence of X such that
    // the digit just after X
    // is greater than X is found
    // then find last occurrence of X
    if (index == -1) {
        for (int i = N.length() - 1; i >= 0; i--) {
            if (N[i] == X) {
                index = i;
                break;
            }
        }
    }
 
    // Construct answer using all characters
    // in string N except index
    string ans = "";
    for (int i = 0; i < N.length(); i++) {
        if (i != index)
            ans = ans + N[i];
    }
 
    return ans;
}
 
int main()
{
 
    string N = "2342";
    char X = '2';
    cout << removeX(N, X) << endl;
    return 0;
}
 
// This code is contributed by Ishan Khandelwal

Java

// Java code to  implement the approach
 
import java.io.*;
 
class GFG {
   
    // Function to find the largest number
    public static String removeX(String N, char X)
    {
        // Stores the index of X 
        // that has to be removed
        int index = -1;
 
        // Find leftmost occurrence of X 
        // such that the digit just after X 
        // is greater than X
        for (int i = 0; i < N.length() - 1; 
             i++) {
            if (N.charAt(i) == X
                && N.charAt(i) - '0'
                    < N.charAt(i + 1) - '0') {
                 
                // Update index and break
                index = i;
                break;
            }
        }
 
        // If no occurrence of X such that 
        // the digit just after X 
        // is greater than X is found 
        // then find last occurrence of X
        if (index == -1) {
            for (int i = N.length() - 1; 
                 i >= 0; i--) {
                if (N.charAt(i) == X) {
                    index = i;
                    break;
                }
            }
        }
 
        // Construct answer using all characters 
        // in string N except index
        String ans = "";
        for (int i = 0; i < N.length(); i++) {
            if (i != index)
                ans = ans + N.charAt(i);
        }
 
        return ans;
    }  
   
    // Driver code
    public static void main(String[] args)
    {
        String N = "2342";
        char X = '2';
       
        // Function call
        System.out.println(removeX(N, X));
    }
}

Python3

# Python code to  implement the approach
def removeX(N, X):
   
    # Stores the index of X
    # that has to be removed
    index = -1;
 
    # Find leftmost occurrence of X
    # such that the digit just after X
    # is greater than X
    for i in range(len(N) - 1):
        if (N[i] == X and ord(N[i]) - ord('0') < ord(N[i + 1]) - ord('0')):
 
            # Update index and break
            index = i;
            break;
 
    # If no occurrence of X such that
    # the digit just after X
    # is greater than X is found
    # then find last occurrence of X
    if (index == -1):
        for i in range(len(N), -1, -1):
            if (N[i] == X):
                index = i;
                break;
             
 
    # Construct answer using all characters
    # in string N except index
    ans = "";
    for i in range(len(N)):
        if (i != index):
            ans = ans + N[i];
     
 
    return ans;
 
N = "2342";
X = '2';
print(removeX(N, X));
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find the largest number
  public static string removeX(string N, char X)
  {
    // Stores the index of X 
    // that has to be removed
    int index = -1;
 
    // Find leftmost occurrence of X 
    // such that the digit just after X 
    // is greater than X
    for (int i = 0; i < N.Length - 1; 
         i++) {
      if (N[i] == X
          && N[i] - '0'
          < N[i + 1] - '0') {
 
        // Update index and break
        index = i;
        break;
      }
    }
 
    // If no occurrence of X such that 
    // the digit just after X 
    // is greater than X is found 
    // then find last occurrence of X
    if (index == -1) {
      for (int i = N.Length - 1; 
           i >= 0; i--) {
        if (N[i] == X) {
          index = i;
          break;
        }
      }
    }
 
    // Construct answer using all characters 
    // in string N except index
    string ans = "";
    for (int i = 0; i < N.Length; i++) {
      if (i != index)
        ans = ans + N[i];
    }
 
    return ans;
  }  
 
  // Driver Code
  public static void Main()
  {
    string N = "2342";
    char X = '2';
 
    // Function call
    Console.Write(removeX(N, X));
  }
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
// Javascript code to  implement the approach
function removeX(N, X)
{
   
    // Stores the index of X
    // that has to be removed
    let index = -1;
 
    // Find leftmost occurrence of X
    // such that the digit just after X
    // is greater than X
    for (let i = 0; i < N.length - 1; i++) {
        if (N[i] == X && N[i] - '0' < N[i + 1] - '0') {
 
            // Update index and break
            index = i;
            break;
        }
    }
 
    // If no occurrence of X such that
    // the digit just after X
    // is greater than X is found
    // then find last occurrence of X
    if (index == -1) {
        for (let i = N.length - 1; i >= 0; i--) {
            if (N[i] == X) {
                index = i;
                break;
            }
        }
    }
 
    // Construct answer using all characters
    // in string N except index
    let ans = "";
    for (let i = 0; i < N.length; i++) {
        if (i != index)
            ans = ans + N[i];
    }
 
    return ans;
}
 
let N = "2342";
let X = '2';
document.write(removeX(N, X));
 
// This code is contributed by Samim Hossain Mondal.
</script>

Output

Time Complexity: O(N)
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!