Maximize array sum by concatenating corresponding elements of given two arrays
Given two array A[] and B[] of the same length, the task is to find the maximum array sum that can be formed by joining the corresponding elements of the array in any order.
Input: A[] = {1, 2, 3, 4, 5}, B[] = {3, 2, 1, 4, 5}
Output: 183
Explanation:
Numbers formed by joining the digits of the elements are –
Join(A[0], B[0]) = Join(1, 3) = 13 or 31
Join(A[1], B[1]) = Join(2, 2) = 22
Join(A[2], B[2]) = Join(3, 1) = 31 or 13
Join(A[3], B[3]) = Join(4, 4) = 44
Join(A[4], B[4]) = Join(5, 5) = 55
Therefore for maximum sum, the array will be {31, 22, 31, 44, 55} with sum = 183
Input: A[] = {11, 23, 38, 43, 59}, B[] = {36, 24, 17, 40, 56}
Output: 19850
Explanation:
Numbers formed by joining the digits of the elements are –
Join(A[0], B[0]) = Join(11, 36) = 1136 or 3611
Join(A[1], B[1]) = Join(23, 24) = 2324 or 2423
Join(A[2], B[2]) = Join(38, 17) = 3817 or 1738
Join(A[3], B[3]) = Join(43, 40) = 4340 or 4043
Join(A[4], B[4]) = Join(59, 56) = 5956 or 5659
Therefore for maximum sum, the array will be {3611, 2423, 3817, 4340, 5956} with sum = 19850
Approach: The idea is to iterate over the array and for each corresponding element of the array
- join them together by iterating over the digits of one number and add the digits into another number which can be defined as follows:
// Join the numbers for digits in numberA: numberB = numberB*10 + digit
- Similarly, join the numbers in reverse order and take the maximum of those numbers.
- Update the corresponding element of the resultant array with the maximum among the two.
- Similarly find all elements of the resultant array and compute the sum.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // maximum array sum by concatenating // corresponding elements of given two arrays #include <bits/stdc++.h> using namespace std; // Function to join the two numbers int joinNumbers( int numA, int numB) { int revB = 0; // Loop to reverse the digits // of the one number while (numB > 0) { revB = revB * 10 + (numB % 10); numB = numB / 10; } // Loop to join two numbers while (revB > 0) { numA = numA * 10 + (revB % 10); revB = revB / 10; } return numA; } // Function to find the maximum array sum int findMaxSum( int A[], int B[], int n) { int maxArr[n]; // Loop to iterate over the two // elements of the array for ( int i = 0; i < n; ++i) { int X = joinNumbers(A[i], B[i]); int Y = joinNumbers(B[i], A[i]); int mx = max(X, Y); maxArr[i] = mx; } // Find the array sum int maxAns = 0; for ( int i = 0; i < n; i++) { maxAns += maxArr[i]; } // Return the array sum return maxAns; } // Driver Code int main() { int N = 5; int A[5] = { 11, 23, 38, 43, 59 }; int B[5] = { 36, 24, 17, 40, 56 }; cout << findMaxSum(A, B, N); } |
Java
// Java implementation to find the // maximum array sum by concatenating // corresponding elements of given two arrays import java.io.*; class GFG { // Function to join the two numbers static int joinNumbers( int numA, int numB) { int revB = 0 ; // Loop to reverse the digits // of the one number while (numB > 0 ) { revB = revB * 10 + (numB % 10 ); numB = numB / 10 ; } // Loop to join two numbers while (revB > 0 ) { numA = numA * 10 + (revB % 10 ); revB = revB / 10 ; } return numA; } // Function to find the maximum array sum static int findMaxSum( int A[], int B[], int n) { int maxArr[] = new int [n]; // Loop to iterate over the two // elements of the array for ( int i = 0 ; i < n; ++i) { int X = joinNumbers(A[i], B[i]); int Y = joinNumbers(B[i], A[i]); int mx = Math.max(X, Y); maxArr[i] = mx; } // Find the array sum int maxAns = 0 ; for ( int i = 0 ; i < n; i++) { maxAns += maxArr[i]; } // Return the array sum return maxAns; } // Driver Code public static void main(String args[]) { int N = 5 ; int A[] = { 11 , 23 , 38 , 43 , 59 }; int B[] = { 36 , 24 , 17 , 40 , 56 }; System.out.println(findMaxSum(A, B, N)); } } // This code is contributed by rutvik_56 |
Python3
# Python3 implementation to find the # maximum array sum by concatenating # corresponding elements of given two arrays # Function to join the two numbers def joinNumbers(numA, numB): revB = 0 # Loop to reverse the digits # of the one number while (numB > 0 ): revB = revB * 10 + (numB % 10 ) numB = numB / / 10 # Loop to join two numbers while (revB > 0 ): numA = numA * 10 + (revB % 10 ) revB = revB / / 10 return numA # Function to find the maximum array sum def findMaxSum(A, B, n): maxArr = [ 0 for i in range (n)] # Loop to iterate over the two # elements of the array for i in range (n): X = joinNumbers(A[i], B[i]) Y = joinNumbers(B[i], A[i]) mx = max (X, Y) maxArr[i] = mx # Find the array sum maxAns = 0 for i in range (n): maxAns + = maxArr[i] # Return the array sum return maxAns # Driver Code if __name__ = = '__main__' : N = 5 A = [ 11 , 23 , 38 , 43 , 59 ] B = [ 36 , 24 , 17 , 40 , 56 ] print (findMaxSum(A, B, N)) # This code is contributed by Samarth |
C#
// C# implementation to find the // maximum array sum by concatenating // corresponding elements of given two arrays using System; class GFG{ // Function to join the two numbers static int joinNumbers( int numA, int numB) { int revB = 0; // Loop to reverse the digits // of the one number while (numB > 0) { revB = revB * 10 + (numB % 10); numB = numB / 10; } // Loop to join two numbers while (revB > 0) { numA = numA * 10 + (revB % 10); revB = revB / 10; } return numA; } // Function to find the maximum array sum static int findMaxSum( int []A, int []B, int n) { int []maxArr = new int [n]; // Loop to iterate over the two // elements of the array for ( int i = 0; i < n; ++i) { int X = joinNumbers(A[i], B[i]); int Y = joinNumbers(B[i], A[i]); int mx = Math.Max(X, Y); maxArr[i] = mx; } // Find the array sum int maxAns = 0; for ( int i = 0; i < n; i++) { maxAns += maxArr[i]; } // Return the array sum return maxAns; } // Driver Code public static void Main(String []args) { int N = 5; int []A = { 11, 23, 38, 43, 59 }; int []B = { 36, 24, 17, 40, 56 }; Console.WriteLine(findMaxSum(A, B, N)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to find the // maximum array sum by concatenating // corresponding elements of given two arrays // Function to join the two numbers function joinNumbers(numA, numB) { var revB = 0; // Loop to reverse the digits // of the one number while (numB > 0) { revB = revB * 10 + (numB % 10); numB = parseInt(numB / 10); } // Loop to join two numbers while (revB > 0) { numA = numA * 10 + (revB % 10); revB = parseInt( revB / 10); } return numA; } // Function to find the maximum array sum function findMaxSum(A, B, n) { var maxArr = Array(n).fill(0); // Loop to iterate over the two // elements of the array for ( var i = 0; i < n; ++i) { var X = joinNumbers(A[i], B[i]); var Y = joinNumbers(B[i], A[i]); var mx = Math.max(X, Y); maxArr[i] = mx; } // Find the array sum var maxAns = 0; for ( var i = 0; i < n; i++) { maxAns += maxArr[i]; } // Return the array sum return maxAns; } // Driver Code var N = 5; var A = [ 11, 23, 38, 43, 59 ]; var B = [ 36, 24, 17, 40, 56 ]; document.write( findMaxSum(A, B, N)); </script> |
19850
Time Complexity: O(n * (log10numB + log10revB))
Auxiliary Space: O(n)