Given two natural numbers N1 and N2, the task is to find the maximum sum possible after swapping of a single digit between them.
Examples:
Input: N1 = 984788, N2 = 706
Output: 988194
Explanation:
Swapping 4 from N1 with 7 from N2, we get N1 = 987788 and N2 = 406
Sum = 988194Input: N1 = 9987, N2 = 123
Output: 10740
Explanation:
Swapping 8 from N1 with 1 from N2, we get N1 = 9917 and N2 = 823
Sum = 10740
Approach:
- Compare N1 and N2 and store the digits of the larger of the two in array arr1 and that of the smaller in arr2 respectively.
- If both the numbers are of different lengths, find the index of maximum element in arr2, and the most significant index in arr1, and swap them to maximize the sum.
- If both the numbers are of same length,
- Iterate both the arrays arr1 and arr2 at the same time.
- For each digit at index i in both the arrays, find the difference between the current digit and the largest digit left to index ‘i’.
- Compare the difference to find the most significant digit and most significant index, whose value needs to be swapped.
- Restore the new numbers from arr1 and arr2 and calculate the maximized sum.
Below code is the implementation of the above approach:
C++
// C++ program to maximise the sum of two// Numbers using at most one swap between them#include <bits/stdc++.h>using namespace std;#define MAX 100// Function to maximize the sum// by swapping only one digitvoid findMaxSum(int n1, int n2){ int arr1[MAX] = { 0 }, arr2[MAX] = { 0 }; int l1 = 0, l2 = 0; int max1 = max(n1, n2); int min1 = min(n1, n2); // Store digits of max(n1, n2) for (int i = max1; i > 0; i /= 10) arr1[l1++] = (i % 10); // Store digits of min(n1, n2) for (int i = min1; i > 0; i /= 10) arr2[l2++] = (i % 10); int f = 0; // If length of the two numbers // are unequal if (l1 != l2) { // Find the most significant number // and the most significant index // for swapping int index = (max_element(arr2, arr2 + l2) - arr2); for (int i = l1 - 1; i > (l2 - 1); i--) { if (arr1[i] < arr2[index]) { swap(arr1[i], arr2[index]); f = 1; break; } } } // If both numbers are // of equal length if (f != 1) { int index1 = 0, index2 = 0; int diff1 = 0, diff2 = 0; for (int i = l2 - 1; i >= 0; i--) { // Fetch the index of current maximum // digit present in both the arrays index1 = (max_element(arr1, arr1 + i) - arr1); index2 = (max_element(arr2, arr2 + i) - arr2); // Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); // Find the most significant index // and the most significant digit // to be swapped if (diff1 > 0 || diff2 > 0) { if (diff1 > diff2) { swap(arr1[i], arr2[index2]); break; } else if (diff2 > diff1) { swap(arr2[i], arr1[index1]); break; } else if (diff1 == diff2) { if (index1 <= index2) { swap(arr2[i], arr1[index1]); break; } else if (index2 <= index1) { swap(arr1[i], arr2[index2]); break; } } } } } // Restore the new numbers int f_n1 = 0, f_n2 = 0; for (int i = l1 - 1; i >= 0; i--) { f_n1 = (f_n1 * 10) + arr1[i]; f_n2 = (f_n2 * 10) + arr2[i]; } // Display the maximized sum cout << (f_n1 + f_n2) << "\n";}// Driver functionint main(){ int N1 = 9987; int N2 = 123; findMaxSum(N1, N2); return 0;} |
Java
// Java program to maximise the sum of two // Numbers using at most one swap between them import java.util.*;class GFG{ static int MAX = 100; static int max_element(int arr[], int pos) { int tmp = arr[0]; int ind = 0; for(int i = 1; i < pos; i++) { if (tmp < arr[i]) { tmp = arr[i]; ind = i; } } return ind; } // Function to maximize the sum // by swapping only one digit static void findMaxSum(int n1, int n2) { int []arr1 = new int[MAX]; int []arr2 = new int[MAX]; int l1 = 0, l2 = 0; int max1 = Math.max(n1, n2); int min1 = Math.min(n1, n2); // Store digits of max(n1, n2) for(int i = max1; i > 0; i /= 10) arr1[l1++] = (i % 10); // Store digits of min(n1, n2) for(int i = min1; i > 0; i /= 10) arr2[l2++] = (i % 10); int f = 0; // If length of the two numbers // are unequal if (l1 != l2) { // Find the most significant number // and the most significant index // for swapping int index = (max_element(arr2, l2)); for(int i = l1 - 1; i > (l2 - 1); i--) { if (arr1[i] < arr2[index]) { int tmp = arr1[i]; arr1[i] = arr2[index]; arr2[index] = tmp; f = 1; break; } } } // If both numbers are // of equal length if (f != 1) { int index1 = 0, index2 = 0; int diff1 = 0, diff2 = 0; for(int i = l2 - 1; i >= 0; i--) { // Fetch the index of current maximum // digit present in both the arrays index1 = (max_element(arr1, i)); index2 = (max_element(arr2, i)); // Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); // Find the most significant index // and the most significant digit // to be swapped if (diff1 > 0 || diff2 > 0) { if (diff1 > diff2) { int tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } else if (diff2 > diff1) { int tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (diff1 == diff2) { if (index1 <= index2) { int tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (index2 <= index1) { int tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } } } } } // Restore the new numbers int f_n1 = 0, f_n2 = 0; for(int i = l1 - 1; i >= 0; i--) { f_n1 = (f_n1 * 10) + arr1[i]; f_n2 = (f_n2 * 10) + arr2[i]; } // Display the maximized sum System.out.println(f_n1 + f_n2); } // Driver code public static void main(String[] args) { int N1 = 9987; int N2 = 123; findMaxSum(N1, N2); } } // This code is contributed by grand_master |
Python3
# Python program to maximise the sum of two# Numbers using at most one swap between themMAX = 100# Function to maximize the sum# by swapping only one digitdef findMaxSum(n1, n2): arr1 = [0]*(MAX) arr2 = [0]*(MAX) l1 = 0 l2 = 0 max1 = max(n1, n2); min1 = min(n1, n2); # Store digits of max(n1, n2) i = max1 while i > 0: arr1[l1] = (i % 10) l1 += 1 i //= 10 # Store digits of min(n1, n2) i = min1 while i > 0: arr2[l2] = (i % 10) l2 += 1 i //= 10 f = 0 # If length of the two numbers # are unequal if (l1 != l2): # Find the most significant number # and the most significant index # for swapping index = arr2.index(max(arr2)) for i in range ( l1 - 1, (l2 - 1), -1): if (arr1[i] < arr2[index]): (arr1[i], arr2[index]) = (arr2[index],arr1[i]) f = 1 break # If both numbers are # of equal length if (f != 1): index1 = 0 index2 = 0 diff1 = 0 diff2 = 0 for i in range( l2 - 1, -1,-1): # Fetch the index of current maximum # digit present in both the arrays index1 = arr1.index(max(arr1[:i])) index2 = arr2.index(max(arr2[:i])) # Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); # Find the most significant index # and the most significant digit # to be swapped if (diff1 > 0 or diff2 > 0): if (diff1 > diff2): arr1[i], arr2[index2] = arr2[index2],arr1[i] break elif (diff2 > diff1): arr2[i], arr1[index1] = arr1[index1],arr2[i] break elif (diff1 == diff2): if (index1 <= index2): arr2[i], arr1[index1] = arr1[index1],arr2[i] break elif (index2 <= index1): arr1[i], arr2[index2] = arr2[index2],arr1[i] break; # Restore the new numbers f_n1 = 0 f_n2 = 0 for i in range (l1 - 1, -1,-1): f_n1 = (f_n1 * 10) + arr1[i] f_n2 = (f_n2 * 10) + arr2[i] # Display the maximized sum print(f_n1 + f_n2)# Driver functionN1 = 9987N2 = 123findMaxSum(N1, N2)# This code is contributed by ANKITKUMAR34 |
C#
// C# program to maximise the sum of two// Numbers using at most one swap between themusing System;class GFG{static int MAX = 100;static int max_element(int []arr, int pos){ int tmp = arr[0]; int ind = 0; for(int i = 1; i < pos; i++) { if (tmp < arr[i]) { tmp = arr[i]; ind = i; } } return ind;}// Function to maximize the sum// by swapping only one digitstatic void findMaxSum(int n1, int n2){ int []arr1 = new int[MAX]; int []arr2 = new int[MAX]; int l1 = 0, l2 = 0; int max1 = Math.Max(n1, n2); int min1 = Math.Min(n1, n2); // Store digits of max(n1, n2) for(int i = max1; i > 0; i /= 10) arr1[l1++] = (i % 10); // Store digits of min(n1, n2) for(int i = min1; i > 0; i /= 10) arr2[l2++] = (i % 10); int f = 0; // If length of the two numbers // are unequal if (l1 != l2) { // Find the most significant number // and the most significant index // for swapping int index = (max_element(arr2,l2)); for(int i = l1 - 1; i > (l2 - 1); i--) { if (arr1[i] < arr2[index]) { int tmp = arr1[i]; arr1[i] = arr2[index]; arr2[index] = tmp; f = 1; break; } } } // If both numbers are // of equal length if (f != 1) { int index1 = 0, index2 = 0; int diff1 = 0, diff2 = 0; for(int i = l2 - 1; i >= 0; i--) { // Fetch the index of current maximum // digit present in both the arrays index1 = (max_element(arr1, i)); index2 = (max_element(arr2, i)); // Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); // Find the most significant index // and the most significant digit // to be swapped if (diff1 > 0 || diff2 > 0) { if (diff1 > diff2) { int tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } else if (diff2 > diff1) { int tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (diff1 == diff2) { if (index1 <= index2) { int tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (index2 <= index1) { int tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } } } } } // Restore the new numbers int f_n1 = 0, f_n2 = 0; for(int i = l1 - 1; i >= 0; i--) { f_n1 = (f_n1 * 10) + arr1[i]; f_n2 = (f_n2 * 10) + arr2[i]; } // Display the maximized sum Console.Write(f_n1 + f_n2);}// Driver codepublic static void Main(string[] args){ int N1 = 9987; int N2 = 123; findMaxSum(N1, N2);}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript program to maximise the sum of two// Numbers using at most one swap between themlet MAX = 100; function max_element(arr, pos){ let tmp = arr[0]; let ind = 0; for(let i = 1; i < pos; i++) { if (tmp < arr[i]) { tmp = arr[i]; ind = i; } } return ind;} // Function to maximize the sum// by swapping only one digitfunction findMaxSum(n1, n2){ let arr1 = Array.from({length: MAX}, (_, i) => 0); let arr2 = Array.from({length: MAX}, (_, i) => 0); let l1 = 0, l2 = 0; let max1 = Math.max(n1, n2); let min1 = Math.min(n1, n2); // Store digits of max(n1, n2) for(let i = max1; i > 0; i = Math.floor(i / 10)) arr1[l1++] = (i % 10); // Store digits of min(n1, n2) for(let i = min1; i > 0; i = Math.floor(i / 10)) arr2[l2++] = (i % 10); let f = 0; // If length of the two numbers // are unequal if (l1 != l2) { // Find the most significant number // and the most significant index // for swapping let index = (max_element(arr2, l2)); for(let i = l1 - 1; i > (l2 - 1); i--) { if (arr1[i] < arr2[index]) { let tmp = arr1[i]; arr1[i] = arr2[index]; arr2[index] = tmp; f = 1; break; } } } // If both numbers are // of equal length if (f != 1) { let index1 = 0, index2 = 0; let diff1 = 0, diff2 = 0; for(let i = l2 - 1; i >= 0; i--) { // Fetch the index of current maximum // digit present in both the arrays index1 = (max_element(arr1, i)); index2 = (max_element(arr2, i)); // Compute the difference diff1 = (arr2[index2] - arr1[i]); diff2 = (arr1[index1] - arr2[i]); // Find the most significant index // and the most significant digit // to be swapped if (diff1 > 0 || diff2 > 0) { if (diff1 > diff2) { let tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } else if (diff2 > diff1) { let tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (diff1 == diff2) { if (index1 <= index2) { let tmp = arr1[index1]; arr1[index1] = arr2[i]; arr2[i] = tmp; break; } else if (index2 <= index1) { let tmp = arr1[i]; arr1[i] = arr2[index2]; arr2[index2] = tmp; break; } } } } } // Restore the new numbers let f_n1 = 0, f_n2 = 0; for(let i = l1 - 1; i >= 0; i--) { f_n1 = (f_n1 * 10) + arr1[i]; f_n2 = (f_n2 * 10) + arr2[i]; } // Display the maximized sum document.write(f_n1 + f_n2);}// Driver Code let N1 = 9987; let N2 = 123; findMaxSum(N1, N2); </script> |
Output:
10740
Time Complexity: O(n)
Auxiliary Space: O(MAX)
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!
