Find two numbers with maximum sum formed by array digits
Given an integer array 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.
For example,
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 the given digits 0–9 when the largest digit appears first, the second-largest digit appears second, and so on… finally, the smallest digit appears at the end. We can easily extend this logic to solve this problem.
The idea is to sort the given array in descending order and construct two numbers x and y by picking alternate digits from the array, where x is filled with digits at the odd indices, y is filled with digits at the even index of the sorted array.
Following is the C++, Java, and Python implementation of the idea:
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 37 38 39 40 41 42 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Find two numbers with a maximum sum formed by digits of an array pair<int, int> findMaximum(vector<int> input) // no-ref, no-const { // base case: invalid input if (input.size() <= 1) { return make_pair(-1, -1); } // sort the array in descending order sort(input.rbegin(), input.rend()); // fill `x` with digits at the odd indices of the 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 the 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); } int main() { vector<int> input = { 4, 6, 2, 7, 9, 8 }; pair<int, int> p = findMaximum(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
Java
|
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 37 38 39 40 |
import java.util.Arrays; import java.util.Comparator; class Main { // Find two numbers with a maximum sum formed by digits of an array public static void findMaximum(Integer[] input) { // base case if (input.length <= 1) { return; } // sort the array in descending order Arrays.sort(input, Comparator.reverseOrder()); // fill `x` with digits at the odd indices of the sorted array int x = 0; for (int i = 0; i < input.length; i = i + 2) { x = x * 10 + input[i]; } // fill `y` with digits at the even indices of the sorted array int y = 0; for (int i = 1; i < input.length; i = i + 2) { y = y * 10 + input[i]; } // print `x` and `y` System.out.println("The two numbers with maximum sum are " + x + " and " + y); } public static void main(String[] args) { Integer[] input = { 4, 6, 2, 7, 9, 8 }; findMaximum(input); } } |
Output:
The two numbers with maximum sum are 974 and 862
Python
|
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 |
# Find two numbers with a maximum sum formed by digits of a list def findMaximum(input): # base case if len(input) <= 1: return # sort the list in descending order input.sort(reverse=True) # fill `x` with digits at the odd indices of the sorted list x = 0 for i in range (0, len(input), 2): x = x * 10 + input[i] # fill `y` with digits at the even indices of the sorted list y = 0 for i in range (1, len(input), 2): y = y * 10 + input[i] # print `x` and `y` print(f'The two numbers with maximum sum are {x} and {y}') if __name__ == '__main__': input = [4, 6, 2, 7, 9, 8] findMaximum(input) |
Output:
The two numbers with maximum sum are 974 and 862
The time complexity of the above solution is O(n.log(n)) and doesn’t require any extra space, where n is the size of the input.
Exercise: Modify the solution to find two numbers with minimum sum.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)