Find two numbers with maximum sum formed by array digits

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.


 

For example,


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++

Download   Run Code

Output:

The two numbers with maximum sum are 974 and 862

Java

Download   Run Code

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Paul
Guest
Paul

98764 + 2

Coder
Guest
Coder

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