Maximize the number formed by replacing adjacent digits with their sum
Given a number N without leading 0s, the task is to find the maximum number formed after replacing any two adjacent digits by their sum only once.
Examples:
Input: 10057
Output: 10012
Explanation: 10012 is the maximum number that we can form since 5+7=12.Input: 30
Output: 3 .
Explanation: 3+0=3 the only option .
Approach: The problem can be solved based on the following observation:
There can be two cases:
If there is at least one pair having sum greater than or equal to 10:
- The sum of the numbers will always be less than the number formed by the two adjacent digits but the number of digits will be same.
- So find such a pair that is at the right end of the number and replace the rightmost such pair.
If there is no such pair:
- Then the newly formed number will always have on less digit than N.
- To maximize the number it is optimal to replace the leftmost such pair because the sum will always be greater than any of the digits.
Follow the steps mentioned below to implement the idea:
- First of all, we will convert the given number to a string for sake of convenience. Let the string be s.
- Consider there is a pair whose sum is greater than 10:
- Traverse from the back.
- If such a pair is found replace them with the sum of those digits.
- Otherwise, there is no such pair.
- Replace the leftmost pair.
- The leftmost pair is formed by the first two digits. So replace them with their sum.
- The number formed is the required answer.
Below is the implementation of the above approach :
C++14
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to return the required maximum number string compute( int N) { // To compare adjacent elements easily string s = to_string(N); int n = s.size(); // Flag to check whether it contains // any adjacent pair whose sum is >=10 or not bool f = 0; int mx = 0, pos = -1; // Resultant string after one operation string ans; if (n < 2) return ans; for ( int i = 0; i < n - 1; i++) { int k = s[i] - '0' ; int p = s[i + 1] - '0' ; int num = k + p; if (num >= 10) { f = 1; mx = num; // Position is the last position // whose sum of adjacent elements // are greater than 10 . pos = i; } } if (f) { for ( int i = 0; i <= pos - 1; i++) // Elements till position-1 // will remain as it is ans += s[i]; // mx is the sum of two // adjacent elements ans += to_string(mx); for ( int i = pos + 2; i < n; i++) // Add rest of string to ans ans += s[i]; } else { // First digit int k = s[0] - '0' ; // Second digit int p = s[1] - '0' ; int temp = k + p; // temp is the sum of first two digit ans += to_string(temp); for ( int i = 2; i < n; i++) // Add rest of elements to ans ans += s[i]; } return ans; } // Driver code int main() { int N = 10057; // Function call cout << compute(N) << endl; return 0; } |
Java
// java code to implement the approach class GFG { // Function to return the required maximum number static String compute( int N) { // To compare adjacent elements easily String s = Integer.toString(N); int n = s.length(); // Flag to check whether it contains // any adjacent pair whose sum is >=10 or not boolean f = false ; int mx = 0 , pos = - 1 ; // Resultant string after one operation String ans= "" ; if (n < 2 ) return ans; for ( int i = 0 ; i < n - 1 ; i++) { int k = s.charAt(i)- '0' ; int p = s.charAt(i+ 1 ) - '0' ; int num = k + p; if (num >= 10 ) { f = true ; mx = num; // Position is the last position // whose sum of adjacent elements // are greater than 10 . pos = i; } } if (f) { for ( int i = 0 ; i <= pos - 1 ; i++){ // Elements till position-1 // will remain as it is ans = ans+s.charAt(i); } // mx is the sum of two // adjacent elements ans += Integer.toString(mx); for ( int i = pos + 2 ; i < n; i++) // Add rest of string to ans ans += s.charAt(i); } else { // First digit int k = s.charAt( 0 ) - '0' ; // Second digit int p = s.charAt( 1 ) - '0' ; int temp = k + p; // temp is the sum of first two digit ans += String.valueOf(temp); for ( int i = 2 ; i < n; i++) // Add rest of elements to ans ans += s.charAt(i); } return ans; } public static void main(String[] args) { int N = 10057 ; // Function call System.out.println(compute(N)); } } // this code is contributed by ksam24000 |
Python3
# Python code to implement the approach # Function to return the required maximum number def compute(N) - > str : # To compare adjacent elements easily s = str (N) n = len (s) # Flag to check whether it contains any adjacent pair whose sum is >=10 or not f = False mx = 0 pos = - 1 # Resultant string after one operation ans = "" if (n < 2 ): return ans for i in range ( 0 ,n - 1 ): k = ord (s[i]) - ord ( '0' ) p = ord (s[i + 1 ]) - ord ( '0' ) num = k + p if (num > = 10 ): f = True mx = num # Position is the last position whose sum of adjacent elements are greater than 10 . pos = i if (f): for i in range ( 0 ,pos): # Elements till position-1 will remain as it is ans + = s[i] # mx is the sum of two adjacent elements ans + = str (mx) for i in range (pos + 2 ,n): # Add rest of string to ans ans + = s[i] else : # First digit k = ord (s[ 0 ]) - ord ( '0' ) # Second digit p = ord (s[ 1 ]) - ord ( '0' ) temp = k + p # temp is the sum of first two digit ans + = str (temp) for i in range ( 2 ,n): # Add rest of elements to ans ans + = s[i] return ans # Driver code if __name__ = = '__main__' : N = 10057 # Function call print (compute(N)) # This code is contributed by ajaymakvana. |
C#
// C# program to implement above approach using System; using System.Collections.Generic; class GFG { // Function to return the required maximum number static string compute( int N) { // To compare adjacent elements easily string s = N.ToString(); int n = s.Length; // Flag to check whether it contains // any adjacent pair whose sum is >=10 or not bool f = false ; int mx = 0, pos = -1; // Resultant string after one operation string ans = " " ; if (n < 2) return ans; for ( int i = 0; i < n - 1; i++) { int k = s[i] - '0' ; int p = s[i + 1] - '0' ; int num = k + p; if (num >= 10) { f = true ; mx = num; // Position is the last position // whose sum of adjacent elements // are greater than 10 . pos = i; } } if (f) { for ( int i = 0; i <= pos - 1; i++) // Elements till position-1 // will remain as it is ans += s[i]; // mx is the sum of two // adjacent elements ans += mx.ToString(); for ( int i = pos + 2; i < n; i++) // Add rest of string to ans ans += s[i]; } else { // First digit int k = s[0] - '0' ; // Second digit int p = s[1] - '0' ; int temp = k + p; // temp is the sum of first two digit ans += temp.ToString(); for ( int i = 2; i < n; i++) // Add rest of elements to ans ans += s[i]; } return ans; } // Driver code public static void Main( string [] args) { int N = 10057; // Function call Console.WriteLine(compute(N)); } } // This code is contributed by snjoy_62. |
Javascript
<script> // JS code to implement the approach // Function to return the required maximum number function compute(N) { // To compare adjacent elements easily let s = N.toString(); let n = s.length; // Flag to check whether it contains // any adjacent pair whose sum is >=10 or not let f = 0; let mx = 0, pos = -1; // Resultant string after one operation let ans = "" ; if (n < 2) return ans; for (let i = 0; i < n - 1; i++) { let k = s[i].charCodeAt(0) - '0' .charCodeAt(0); let p = s[i + 1].charCodeAt(0) - '0' .charCodeAt(0); let num = k + p; if (num >= 10) { f = 1; mx = num; // Position is the last position // whose sum of adjacent elements // are greater than 10 . pos = i; } } if (f) { for (let i = 0; i <= pos - 1; i++) // Elements till position-1 // will remain as it is ans += s[i]; // mx is the sum of two // adjacent elements ans += (mx).toString(); for (let i = pos + 2; i < n; i++) // Add rest of string to ans ans += s[i]; } else { // First digit let k = s[0].charCodeAt(0) - '0' - charCodeAt(0); // Second digit let p = s[1].charCodeAt(0) - '0' .charCodeAt(0); let temp = k + p; // temp is the sum of first two digit ans += (temp).toString(); for (let i = 2; i < n; i++) // Add rest of elements to ans ans += s[i]; } return ans; } // Driver code let N = 10057; // Function call document.write(compute(N)); // This code is contributed by Potta Lokesh </script> |
Output
10012
Time Complexity: O(M) where M is the number of digits in the number.
Auxiliary Space: O(M)
Contact Us