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

**Input:** { 4, 6, 2, 7, 9, 8 }

**Output:** The two numbers with maximum sum are 974 and 862

**Input:** { 9, 2, 5, 6, 0, 4 }

**Output:** The two numbers with maximum sum are 952 and 640

We know that a maximum number can be formed from given digits (0-9) when the largest digit appears first, second largest digit appears second, and so on.. finally the smallest digit appears in the end. We can extend the same logic to solve this problem. We start by sorting the specified array in descending order and construct two numbers (say x and y) by picking alternating digits from the array i.e. x is filled with digits at the odd indices and y is filled with digits at the even indices of the sorted array.

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Find two numbers with maximum sum formed by digits of an array pair<int,int> maximumSum(vector<int> input) { // sort the array in descending order sort(input.rbegin(), input.rend()); // fill x with digits at the odd indices of sorted array int x = 0; for (int i = 0; i < input.size(); i = i + 2) x = x * 10 + input[i]; // fill y with digits at the even indices of sorted array int y = 0; for (int i = 1; i < input.size(); i = i + 2) y = y * 10 + input[i]; // return x and y return make_pair(x, y); } // main function int main() { vector<int> input = { 4, 6, 2, 7, 9, 8 }; pair<int,int> p = maximumSum(input); cout << "The two numbers with maximum sum are " << p.first << " and " << p.second; return 0; } |

`Output: `

The two numbers with maximum sum are 974 and 862

**Exercise:** Modify the solution to find two numbers with minimum sum.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

98764 + 2

The difference in number of digits of the two numbers should be ± 1.