Find smallest number formed by inverting digits of given number N

0 0 7 minutes read

Given an integer N, the task is to form a minimum possible positive number (>0) by inverting some digits of N.

Inverting for a digit T is defined as subtracting it from 9 that is 9 – T.

Note: The final number should not start from zero.

Examples:

Input:N = 4545
Output: 4444
Explanation:
The minimum possible number is 4444 by subtracting the two 5 ( 9 – 5 = 4)

Input: N = 9000
Output: 9000
Explanation:
The minimum possible number is 9000 cause the number has to be > 0 and hence 9 cannot be subtracted from itself.

Approach: The idea is to iterate over all the digits in the given number and check if 9 – current_digit is less than the current_digit then replace that digit with 9 – current_digit else don’t change the digit. If the first digit of the number is 9 then don’t change the digit and we can’t have a trailing zero in the new number formed.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to invert the digits of
// integer N to form minimum
// possible number
void number(int num)
{
    // Initialize the array
    int a[20], r, i = 0, j;
 
    // Iterate till the number N exists
    while (num > 0) {
 
        // Last digit of the number N
        r = num % 10;
 
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
 
            // Store the smaller
            // digit in the array
            a[i] = r;
 
        else
            a[i] = 9 - r;
 
        i++;
 
        // Reduce the number each time
        num = num / 10;
    }
 
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0) {
        cout << 9;
        i--;
    }
 
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        cout << a[j];
}
 
// Driver Code
int main()
{
    // Given Number
    long long int num = 4545;
 
    // Function Call
    number(num);
 
    return 0;
}

Java

// Java program for the above approach
class GFG{
  
// Function to invert the digits of
// integer N to form minimum
// possible number
static void number(int num)
{
    // Initialize the array
    int a[] = new int[20];
    int r, i = 0, j;
  
    // Iterate till the number N exists
    while (num > 0)
    {
  
        // Last digit of the number N
        r = num % 10;
  
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
  
            // Store the smaller
            // digit in the array
            a[i] = r;
  
        else
            a[i] = 9 - r;
  
        i++;
  
        // Reduce the number each time
        num = num / 10;
    }
  
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0) 
    {
        System.out.print("9");
        i--;
    }
  
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        System.out.print(a[j]);
}
  
// Driver Code
public static void main(String []args)
{
    // Given Number
     int num = 4545;
  
    // Function Call
    number(num);
}
}
 
// This code is contributed by rock_cool

Python3

# Python3 program for the above approach
 
# Function to invert the digits of
# integer N to form minimum
# possible number
def number(num):
   
    # Initialize the array
    a = [0] * 20
    r, i, j = 0, 0, 0
 
    # Iterate till the number N exists
    while (num > 0):
 
        # Last digit of the number N
        r = num % 10
 
        # Checking if the digit is
        # smaller than 9-digit
        if (9 - r > r):
 
            # Store the smaller
            # digit in the array
            a[i] = r
 
        else:
            a[i] = 9 - r
 
        i += 1
 
        # Reduce the number each time
        num = num // 10
 
    # Check if the digit starts
    # with 0 or not
    if (a[i - 1] == 0):
        print(9, end = "")
        i -= 1
 
    # Print the answer
    for j in range(i - 1, -1, -1):
        print(a[j], end = "")
 
# Driver Code
if __name__ == '__main__':
   
    # Given Number
    num = 4545
 
    # Function Call
    number(num)
 
# This code is contributed by Mohit Kumar

C#

// C# program for the above approach
using System;
class GFG{
   
// Function to invert the digits of
// integer N to form minimum
// possible number
static void number(int num)
{
    // Initialize the array
    int[] a = new int[20];
    int r, i = 0, j;
   
    // Iterate till the number N exists
    while (num > 0)
    {
   
        // Last digit of the number N
        r = num % 10;
   
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
   
            // Store the smaller
            // digit in the array
            a[i] = r;
   
        else
            a[i] = 9 - r;
   
        i++;
   
        // Reduce the number each time
        num = num / 10;
    }
   
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0) 
    {
        Console.Write("9");
        i--;
    }
   
    // Print the answer
    for (j = i - 1; j >= 0; j--)
        Console.Write(a[j]);
}
   
// Driver Code
public static void Main(string []args)
{
    // Given Number
     int num = 4545;
   
    // Function Call
    number(num);
}
}
  
// This code is contributed by Ritik Bansal

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to invert the digits of
// integer N to form minimum
// possible number
function number(num)
{
     
    // Initialize the array
    let a = new Array(20);
    let r, j;
    let i = 0;
 
    // Iterate till the number N exists
    while (num > 0)
    {
         
        // Last digit of the number N
        r = num % 10;
 
        // Checking if the digit is
        // smaller than 9-digit
        if (9 - r > r)
 
            // Store the smaller
            // digit in the array
            a[i] = r;
 
        else
            a[i] = 9 - r;
 
        i++;
 
        // Reduce the number each time
        num = parseInt(num / 10, 10);
    }
 
    // Check if the digit starts
    // with 0 or not
    if (a[i - 1] == 0) 
    {
        document.write(9);
        i--;
    }
 
    // Print the answer
    for(j = i - 1; j >= 0; j--)
        document.write(a[j]);
}
 
// Driver code
 
// Given Number
let num = 4545;
 
// Function Call
number(num);
 
// This code is contributed by divyesh072019
 
</script>

Output

Time Complexity: O(log₁₀N)
Auxiliary Space: O(log₁₀N)

Alternate approach -: To get the minimum number we need to convert all digits at their minimum, so we can get the minimum number after subtracting is 4,3,2,1.

Reason-: We can only get 4 or 3 or 2 or 1 or 0 minimals after subtracting any digit from 9 so If we have 5 or 6 
or 7 or 8 at the first digit then after subtracting from 9 we can get 4 or 3 or 2 or 1, and if these are not
present then that means that we already have minimum 4 or 3 or 2 or 1 at the first digit.

So we will check for every s[i] if 4<s[i]<9 then we will subtract s[i] from 9 and hence will get the desired result.

C++

#include <bits/stdc++.h>
using namespace std;
 
string solve(string s)
{
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if (s[0] != '9' && s[0] > '4') {
        s[0] = '0' + ('9' - s[0]);
    }
 
    // Check for every s[i] from
    // 1 to s.length that 4 < s[i]
    // < 9
    for (int i = 1; i < s.size(); i++) {
        if (s[i] > '4')
            s[i] = '0' + ('9' - s[i]);
    }
    return s;
}
int main()
{
    string s = "27";
    cout << solve(s);
    return 0;
};

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
  static String solve(String s)
  {
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if (s.charAt(0) != '9' && (int)s.charAt(0) > (int)'4') {
      s = (char)((int)'0' + ((int)'9' - (int)s.charAt(0))) + 
        s.substring(1, s.length());
    }
 
    // // Check for every s[i] from
    // // 1 to s.length that 4 < s[i]
    // // < 9
    for (int i = 1; i < s.length(); i++) {
      if ((int)s.charAt(i) > (int)'4')
        s = s.substring(0, i) + (char)((int)'0' + ((int)'9' - (int)s.charAt(i))) + s.substring(i+1,s.length());
    }
    return s;
  }
 
  // Driver Code
  public static void main(String args[])
  {
    String s = "27";
    System.out.println(solve(s));
  }
}
 
// This code is contributed by shinjanpatra.

Python3

# Python code for the approach
def solve(s):
 
    # If 4 < s[0] < 9 then subtract to
    # Get the minimum number
    if ord(s[0]) != ord('9') and ord(s[0]) > ord('4'):
        s = s.replace(s[0] , chr(ord('0') + ord('9') - ord(s[0])))
 
    # Check for every s[i] from
    # 1 to s.length that 4 < s[i]
    # < 9
    for i in range(1,len(s)):
        if (s[i] > '4'):
            s = s.replace(s[i] , chr(ord('0') + (ord('9') - ord(s[i]))))
 
    return s
 
# driver code
s = "27"
print(solve(s))
 
# This code is contributed by shinjanpatra

C#

using System;
using System.Collections.Generic;
 
class GFG {
  static string solve(string s)
  {
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if (s[0] != '9' && (int)s[0] > (int)'4') {
      s = (char)((int)'0' + ((int)'9' - (int)s[0]))
        + s.Substring(1, s.Length - 1);
    }
 
    // // Check for every s[i] from
    // // 1 to s.length that 4 < s[i]
    // // < 9
    for (int i = 1; i < s.Length; i++) {
      if ((int)s[i] > (int)'4')
        s = s.Substring(0, i)
        + (char)((int)'0'
                 + ((int)'9' - (int)s[i]))
        + s.Substring(i + 1, s.Length - i - 1);
    }
    return s;
  }
 
  // Driver Code
  public static void Main(string[] args)
  {
    string s = "27";
    Console.WriteLine(solve(s));
  }
}
 
// This code is contributed by phasing17.

Javascript

<script>
 
// JavaScript code for the approach
function solve(s)
{
 
    // If 4 < s[0] < 9 then subtract to
    // Get the minimum number
    if(s.charCodeAt(0) != '9'.charCodeAt(0) && s.charCodeAt(0) > '4'.charCodeAt(0))
        s = s.replace(s[0] , String.fromCharCode('0'.charCodeAt(0) + '9'.charCodeAt(0) - s.charCodeAt(0)))
 
    // Check for every s[i] from
    // 1 to s.length that 4 < s[i]
    // < 9
    for(let i = 1; i < s.length; i++)
    {
        if (s[i] > '4')
        s = s.replace(s[i] , String.fromCharCode('0'.charCodeAt(0) + '9'.charCodeAt(0) - s.charCodeAt(i)))
    }
 
    return s
}
 
// driver code
let s = "27"
document.write(solve(s))
 
// This code is contributed by shinjanpatra
 
</script>

Output

TIME COMPLEXITY – O(N)

SPACE COMPLEXITY – 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!