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 numbervoid 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 Codeint main(){ // Given Number long long int num = 4545; // Function Call number(num); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to invert the digits of// integer N to form minimum// possible numberstatic 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 Codepublic 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 numberdef 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 Codeif __name__ == '__main__': # Given Number num = 4545 # Function Call number(num)# This code is contributed by Mohit Kumar |
C#
// C# program for the above approachusing System;class GFG{ // Function to invert the digits of// integer N to form minimum// possible numberstatic 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 Codepublic 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 numberfunction 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 Numberlet num = 4545;// Function Callnumber(num);// This code is contributed by divyesh072019</script> |
Output
4444
Time Complexity: O(log10N)
Auxiliary Space: O(log10N)
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 approachdef 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 codes = "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 approachfunction 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 codelet s = "27"document.write(solve(s))// This code is contributed by shinjanpatra</script> |
Output
22
TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – 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!
