# 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.

#### 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```