Find the maximum difference after applying the given operations two times on a number️‍🔥

Q: What is Find the maximum difference after applying the given operations two times on a number?

In this article, we will learn Find the maximum difference after applying the given operations two times on a number,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Given an integer N, the task is to find the maximum difference after applying the given operation two times on the given integer.

The operation is defined as follows:

Choose any digit (0-9) from N and replace all instance of the same digit with any other digit (0-9).
N after the operation cannot have leading zeros and also it cannot be equal to zero.

Examples:

Input : N = 777
Output : 888
Explanation: Select digit 7 and replace all it’s occurrences with 9 to get 999. similarly 111 can be obtained by replacing all occurrences of 7 with 1. Hence, the possible maximum difference is 888.

Input : N = 123456
Output : 820000
The numbers after two operation can be 923456 and 103456. Hence, the required maximum difference is 820000.

Explanation: Maximum difference can be obtained by subtraction of the maximum and the minimum number that can be obtained by the given operation on N.

The maximum number can be obtained by picking the first digit of N from the left which is not equal to ‘9’ and replace all the instances of that digit into ‘9’.
Finding the minimum number is a little bit tricky as N cannot have any leading zeros and also it cannot be equal to zero. If the first digit of N from the left is ‘1’, then find the first digit from the left which is greater than ‘1’ and replace all instances of that digit with ‘0’.
Otherwise, if the first digit of N from the left is not equal to ‘1’, then choose that digit and replace all instances of that digit with ‘1’.
Finally, return the difference between the minimum and maximum number as the answer.

Below is the implementation of the above approach:

C++

// C++ program to find the
// maximum difference
// after two given operations
// on a number
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the
// maximum difference
// after two given operations
// on a number
int minDifference(int num)
{
    // Initialize the strings to make operations
    string maximum = to_string(num);
    string minimum = to_string(num);
 
    // Store length of the string
    int n = maximum.size();
 
    // Make the maximum number using
    // the first operation
    for (int i = 0; i < n; i++) {
        // Find the first digit which
        // is not equal to '9'
        if (maximum[i] != '9') {
            // Store the digit for
            // the given operation
            char digit = maximum[i];
            for (int j = i; j < n; j++) {
                // Replace all the selected
                // 'digit' with '9'
                if (maximum[j] == digit)
                    maximum[j] = '9';
            }
            // Break after the operation
            // is completed
            break;
        }
    }
    // Make the minimum number using
    // the second operation
 
    // Check if first digit is equal to '1'
    if (minimum[0] == '1') {
        for (int i = 1; i < n; i++) {
            // Find the first digit which
            // is greater than '1'
            if (minimum[i] - '0' > 1) {
                // Store the digit for
                // the given operation
                char digit = minimum[i];
                for (int j = i; j < n; j++) {
                    // Replace all the selected
                    // 'digit' with '0'
                    if (digit == minimum[j])
                        minimum[j] = '0';
                }
                // Break after the
                // operation is completed
                break;
            }
        }
    }
    else {
        // Select the first digit for
        // the given operation
        char digit = minimum[0];
        for (int i = 0; i < n; i++) {
            // Replace all the selected
            // 'digit' with '1'
            if (minimum[i] == digit)
                minimum[i] = '1';
        }
    }
    // Return the difference after
    // converting into integers
    return (stoi(maximum)
            - stoi(minimum));
}
 
// Driver Code
int main()
{
    int N = 1101157;
 
    cout << minDifference(N);
 
    return 0;
}

Java

// Java program to find the maximum 
// difference after two given operations
// on a number
import java.util.*;
 
class GFG{
 
// Function that returns the
// maximum difference
// after two given operations
// on a number
static int minDifference(int num)
{
     
    // Initialize the strings to make operations
    StringBuilder maximum = 
                  new StringBuilder(Integer.toString(num));
    StringBuilder minimum = 
                  new StringBuilder(Integer.toString(num));
 
    // Store length of the string
    int n = maximum.length();
 
    // Make the maximum number using
    // the first operation
    for(int i = 0; i < n; i++)
    {
        
       // Find the first digit which
       // is not equal to '9'
       if (maximum.charAt(i) != '9')
       {
            
           // Store the digit for
           // the given operation
           char digit = maximum.charAt(i);
           for(int j = i; j < n; j++)
           {
                
              // Replace all the selected
              // 'digit' with '9'
              if (maximum.charAt(j) == digit)
                  maximum.setCharAt(j, '9');
           }
            
           // Break after the operation
           // is completed
           break;
       }
    }
     
    // Make the minimum number
    // using the second operation
    // Check if first digit is equal to '1'
    if (minimum.charAt(0) == '1')
    {
        for(int i = 1; i < n; i++)
        {
            
           // Find the first digit which
           // is greater than '1'
           if (minimum.charAt(i) - '0' > 1) 
           {
                
               // Store the digit for
               // the given operation
               char digit = minimum.charAt(i);
               for(int j = i; j < n; j++) 
               {
                    
                  // Replace all the selected
                  // 'digit' with '0'
                  if (digit == minimum.charAt(j))
                      minimum.setCharAt(j, '0');
               }
                
               // Break after the
               // operation is completed
               break;
           }
        }
    }
    else
    {
         
        // Select the first digit for
        // the given operation
        char digit = minimum.charAt(0);
        for(int i = 0; i < n; i++)
        {
            
           // Replace all the selected
           // 'digit' with '1'
           if (minimum.charAt(i) == digit)
               minimum.setCharAt(i, '1');
        }
    }
     
    // Return the difference after
    // converting into integers
    return (Integer.parseInt(maximum.toString()) -
            Integer.parseInt(minimum.toString()));
}
 
// Driver code
public static void main(String[] args)
{
    int N = 1101157;
 
    System.out.println(minDifference(N));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to find the 
# maximum difference after 
# two given operations 
# on a number 
 
# Function that returns the 
# maximum difference after  
# two given operations 
# on a number 
def minDifference(num):
     
    # Initialize the strings to
    # make operations 
    maximum = list(str(num)); 
    minimum = list(str(num)); 
 
    # Store length of the string 
    n = len(maximum); 
 
    # Make the maximum number using 
    # the first operation 
    for i in range(n): 
         
        # Find the first digit which 
        # is not equal to '9' 
        if (maximum[i] != '9'):
             
            # Store the digit for 
            # the given operation 
            digit = maximum[i]; 
             
            for j in range(i, n):
                 
                # Replace all the selected 
                # 'digit' with '9' 
                if (maximum[j] == digit):
                    maximum[j] = '9'; 
 
            # Break after the operation 
            # is completed 
            break; 
 
    # Make the minimum number using 
    # the second operation 
    # Check if first digit is equal to '1' 
    if (minimum[0] == '1'):
        for i in range(1, n):
             
            # Find the first digit which 
            # is greater than '1' 
            if (ord(minimum[i]) - ord('0') > 1):
                 
                # Store the digit for 
                # the given operation 
                digit = minimum[i]; 
                for j in range(i, n):
                     
                    # Replace all the selected 
                    # 'digit' with '0' 
                    if (digit == minimum[j]):
                        minimum[j] = '0'; 
                 
                # Break after the 
                # operation is completed 
                break; 
         
    else :
         
        # Select the first digit 
        # for the given operation 
        digit = minimum[0]; 
        for i in range(n):
             
            # Replace all the selected 
            # 'digit' with '1' 
            if (minimum[i] == digit):
                minimum[i] = '1'; 
     
    maximum = "".join(maximum)
    minimum = "".join(minimum)
     
    # Return the difference after 
    # converting into integers 
    return (int(maximum) - int(minimum)); 
 
# Driver Code 
if __name__ == "__main__": 
 
    N = 1101157; 
     
    print(minDifference(N)); 
 
# This code is contributed by AnkitRai01 

C#

// C# program to find the maximum
// difference after two given 
// operations on a number 
using System;
using System.Collections.Generic; 
 
class GFG{
     
// Function that returns the 
// maximum difference after 
// two given operations on a 
// number 
static int minDifference(int num) 
{ 
     
    // Initialize the strings to make operations 
    char[] maximum = (num.ToString()).ToCharArray(); 
    char[] minimum = (num.ToString()).ToCharArray(); 
   
    // Store length of the string 
    int n = maximum.Length; 
   
    // Make the maximum number using 
    // the first operation 
    for(int i = 0; i < n; i++) 
    {
         
        // Find the first digit which 
        // is not equal to '9' 
        if (maximum[i] != '9')
        {
             
            // Store the digit for 
            // the given operation 
            char digit = maximum[i]; 
            for(int j = i; j < n; j++)
            {
                 
                // Replace all the selected 
                // 'digit' with '9' 
                if (maximum[j] == digit) 
                    maximum[j] = '9'; 
            } 
             
            // Break after the operation 
            // is completed 
            break; 
        } 
    } 
     
    // Make the minimum number using 
    // the second operation 
   
    // Check if first digit is equal to '1' 
    if (minimum[0] == '1') 
    { 
        for(int i = 1; i < n; i++)
        {
             
            // Find the first digit which 
            // is greater than '1' 
            if (minimum[i] - '0' > 1)
            {
                 
                // Store the digit for 
                // the given operation 
                char digit = minimum[i]; 
                for(int j = i; j < n; j++) 
                {
                     
                    // Replace all the selected 
                    // 'digit' with '0' 
                    if (digit == minimum[j]) 
                        minimum[j] = '0'; 
                } 
                 
                // Break after the 
                // operation is completed 
                break; 
            } 
        } 
    } 
    else
    {
         
        // Select the first digit for 
        // the given operation 
        char digit = minimum[0]; 
        for(int i = 0; i < n; i++) 
        {
             
            // Replace all the selected 
            // 'digit' with '1' 
            if (minimum[i] == digit) 
                minimum[i] = '1'; 
        } 
    } 
     
    // Return the difference after 
    // converting into integers 
    return Convert.ToInt32(string.Join("", maximum)) -
           Convert.ToInt32(string.Join("", minimum));
} 
 
// Driver Code
static void Main()
{
    int N = 1101157; 
     
    Console.Write(minDifference(N)); 
}
}
 
// This code is contributed by divyesh072019

Javascript

<script>
 
// Javascript program to find the maximum
// difference after two given
// operations on a number
 
// Function that returns the
// maximum difference after
// two given operations on a
// number
function minDifference(num)
{
     
    // Initialize the strings to make operations
    let maximum = (num.toString()).split('');
    let minimum = (num.toString()).split('');
 
    // Store length of the string
    let n = maximum.length;
 
    // Make the maximum number using
    // the first operation
    for(let i = 0; i < n; i++)
    {
 
        // Find the first digit which
        // is not equal to '9'
        if (maximum[i] != '9')
        {
 
            // Store the digit for
            // the given operation
            let digit = maximum[i];
            for(let j = i; j < n; j++)
            {
 
                // Replace all the selected
                // 'digit' with '9'
                if (maximum[j] == digit)
                    maximum[j] = '9';
            }
 
            // Break after the operation
            // is completed
            break;
        }
    }
 
    // Make the minimum number using
    // the second operation
 
    // Check if first digit is equal to '1'
    if (minimum[0] == '1')
    {
        for(let i = 1; i < n; i++)
        {
 
            // Find the first digit which
            // is greater than '1'
            if (minimum[i].charCodeAt() -
                '0'.charCodeAt() > 1)
            {
 
                // Store the digit for
                // the given operation
                let digit = minimum[i];
                for(let j = i; j < n; j++)
                {
 
                    // Replace all the selected
                    // 'digit' with '0'
                    if (digit == minimum[j])
                        minimum[j] = '0';
                }
 
                // Break after the
                // operation is completed
                break;
            }
        }
    }
    else
    {
 
        // Select the first digit for
        // the given operation
        let digit = minimum[0];
        for(let i = 0; i < n; i++)
        {
 
            // Replace all the selected
            // 'digit' with '1'
            if (minimum[i] == digit)
                minimum[i] = '1';
        }
    }
 
    // Return the difference after
    // converting into integers
    return parseInt(maximum.join("")) - 
           parseInt(minimum.join(""));
}
 
// Driver code
let N = 1101157;
  
document.write(minDifference(N));
 
// This code is contributed by suresh07
 
</script>

Output:

Time complexity: O((LogN)²), where N is the input number.

Space complexity: O(LogN)