Find two numbers with maximum sum formed by array digits

By | November 28, 2021

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.

[3, 4, 5, 6]

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 