Find two numbers with maximum sum formed by array digits

Problem

Given an integer array having digits between 0 and 9, find two numbers with maximum sum formed using all the array digits. The difference in the number of digits of the two numbers should be ± 1.

Sample Input

[3, 4, 5, 6]

Sample Output

64 and 53

Approach

It is obvious that the largest possible number can be formed by having the largest element of the array as the first digit, second largest as the second digit and so on. Since we have to make two numbers here, we can select alternate numbers of the array for each number after sorting the array.

For example, if we have the array as [3,4,5,6] . After sorting it, we get [6,5,4,3] . We can pick 6, 4 for the first number and 5,3 for the second number. The numbers will be 64 and 53 which will give the largest possible sum. The time complexity of the approach is O(NlogN)

C++ Programming

#include<bits/stdc++.h>
using namespace std;
 
pair<int, int> findMaximum(vector<int> arr)    
{
    sort(arr.rbegin(), arr.rend());
 
    int x = 0;
    for (int i = 0; i < arr.size(); i = i + 2) {
        x = x * 10 + arr[i];
    }
 
    int y = 0;
    for (int i = 1; i < arr.size(); i = i + 2) {
        y = y * 10 + arr[i];
    }
 
    return make_pair(x, y);
}
 
int main()
{
    vector<int> arr = {3, 4, 5, 6};
 
    pair<int, int> ans = findMaximum(arr);
    cout << ans.first <<" "<< ans.second;

}

Output

64 53

Python Programming

def findMaximum(arr):
 
    arr.sort(reverse=True)
 
    x = 0
    for i in range (0, len(arr), 2):
        x = x * 10 + arr[i]
 
    y = 0
    for i in range (1, len(arr), 2):
        y = y * 10 + arr[i]
 
    print(x,y)

arr = [3,4,5,6]
findMaximum(arr)

Output

64 53

Java Programming

import java.util.Arrays;
import java.util.Comparator;
 
class Main
{
    public static void findMaximum(Integer[] arr)
    {
    
        Arrays.sort(arr, Comparator.reverseOrder());

        int x = 0;
        for (int i = 0; i < arr.length; i = i + 2) {
            x = x * 10 + arr[i];
        }
 
        int y = 0;
        for (int i = 1; i < arr.length; i = i + 2) {
            y = y * 10 + arr[i];
        }
 
        System.out.println(x);
        System.out.println(y);
    }
 
    public static void main(String[] args)
    {
        Integer[] arr = { 3,4,5,6 };
 
        findMaximum(arr);
    }
}

Output

64
53

People are also reading:

• Merge Two Sorted Arrays in-place
• Rearrange an array in maximum minimum form
• Rod Cutting Problem
• Sort binary array in linear time
• Maximum of all Subarrays of size K
• Move all zeros present in an array to the end
• Subarray with Sum k
• Find Maximum Subarray Sum
• Longest? ?Bitonic? ?Subarray? ?Problem?
• Dutch National Flag Problem