Maximum possible number with the given operation
Given a positive integer N, the task is to convert this integer to the maximum possible integer without leading zeroes by changing the digits. A digit X can only be changed into a digit Y if X + Y = 9.
Examples:
Input: N = 42
Output: 57
Change 4 -> 5 and 2 -> 7.
Input: N = 1
Output: 8
Approach: Only the digits which are greater than or equal to 5 need to be changed as changing the digits which are less than 5 will result in a larger number. After all the required digits have been updated, check whether the resultant number has a leading zero, if yes then change it to a 9.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the maximum possible // integer that can be obtained from the // given integer after performing // the given operations string maxInt(string str) { // For every digit for ( int i = 0; i < str.length(); i++) { // Digits greater than or equal to 5 // need not to be changed as changing // them will lead to a smaller number if (str[i] < '5' ) { str[i] = ( '9' - str[i]) + '0' ; } } // The resulting integer // cannot have leading zero if (str[0] == '0' ) str[0] = '9' ; return str; } // Driver code int main() { string str = "42" ; cout << maxInt(str); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the maximum possible // integer that can be obtained from the // given integer after performing // the given operations static String maxInt( char str[]) { // For every digit for ( int i = 0 ; i < str.length; i++) { // Digits greater than or equal to 5 // need not to be changed as changing // them will lead to a smaller number if (str[i] < '5' ) { str[i] = ( char )(( '9' - str[i]) + '0' ); } } // The resulting integer // cannot have leading zero if (str[ 0 ] == '0' ) str[ 0 ] = '9' ; String str2 = new String(str); return str2; } // Driver code public static void main (String[] args) { String str = "42" ; System.out.println(maxInt(str.toCharArray())); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the maximum possible # integer that can be obtained from the # given integer after performing # the given operations def maxInt(string): string2 = "" # For every digit for i in range ( 0 , len (string)): # Digits greater than or equal to 5 # need not to be changed as changing # them will lead to a smaller number if (string[i] < '5' ): string2 + = str (( ord ( '9' ) - ord (string[i]))) else : string2 + = str (string[i]) # The resulting integer # cannot have leading zero if (string2[ 0 ] = = '0' ): string2[ 0 ] = '9' return string2 # Driver code if __name__ = = '__main__' : string = "42" print (maxInt(string)) # This code is contributed by ashutosh450 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum possible // integer that can be obtained from the // given integer after performing // the given operations static String maxInt( char []str) { // For every digit for ( int i = 0; i < str.Length; i++) { // Digits greater than or equal to 5 // need not to be changed as changing // them will lead to a smaller number if (str[i] < '5' ) { str[i] = ( char )(( '9' - str[i]) + '0' ); } } // The resulting integer // cannot have leading zero if (str[0] == '0' ) str[0] = '9' ; String str2 = new String(str); return str2; } // Driver code public static void Main (String []args) { String str = "42" ; Console.WriteLine(maxInt(str.ToCharArray())); } } // This code is contributed by Arnab Kundu |
Javascript
<script> // Javascript implementation of the // above approach // Function to return the maximum possible // integer that can be obtained from the // given integer after performing // the given operations function maxInt(str) { // For every digit var str2 = "" ; for ( var i = 0; i < str.length; i++) { // Digits greater than or equal to 5 // need not to be changed as changing // them will lead to a smaller number if (str[i] < '5' ) { var l = ( '9' .charCodeAt(0) - str[i].charCodeAt(0)) + '0' .charCodeAt(0); str2 = str2.concat(String.fromCharCode(l)); } } // The resulting integer // cannot have leading zero if (str2[0] == '0' ) str2[0] = '9' ; return str2; } // Driver code var str = "42" ; document.write(maxInt(str)) // This code is contributed by ShubhamSingh10 </script> |
Output:
57
Time Complexity: O(|str|)
Auxiliary Space: O(1)