Maximize the number formed by replacing adjacent digits with their sum - Coding

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

Time Complexity: O(M) where M is the number of digits in the number.
Auxiliary Space: O(M)

Reffered: https://www.geeksforgeeks.org

Greedy

Related
Find all the factors of given Number and their bitwise XOR
Minimize the size of Array by doing maximum absorptions
Minimize insertions in Array to make ratio of each pair as K
Maximise length of smallest group by dividing Binary String into K groups of same bit
Minimize operations to reduce A or B to 0 by reducing A from B or B from A

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13