Last Updated: 10 Dec, 2020
Find the password
Easy
Spider Man needs to retrieve a secret file stored in the computer of Dr. Octavius. He finds a clue to the password, but since he is running short on time, he asks you for help. Following is the clue provided-
Given ‘N’ DIGITS valued from 0 to 9, the password is the minimum possible sum of two numbers formed by using all the DIGITS only once.
For example - For DIGITS = [4, 3, 2, 7, 1, 9], the minimum sum is 385 which is obtained by adding numbers 137 and 249.
Can you help Spider Man find the password?
Note - The number of DIGITS is always greater than or equal to 2. Hence, the answer will always exist.
Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to be processed. Then the test case follows.
The first line of each test case contains a single integer ‘N’ denoting the number of digits.
The second line of each test case contains ‘N’ single space-separated non-negative integers representing the digits.
Output Format :
For each test case, print the password.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
2 <= N <= 5000
0 <= DIGITS[i] <= 9
Where ‘N’ is the number of digits
Time Limit: 1sec
Approaches
To find the two numbers that add up to the minimum sum, we take into account the following points -
- The count of digits in these two numbers must be equal (or differ by 1 in case of odd N).
- A minimum number can be formed using digits 0 to 9 if the leading digit is smaller than the digit following it i.e. the first digit (or the most significant position) of the number is the smallest, the second digit is larger than the first and so on.
Here is the complete approach -
- We will sort the ‘DIGITS’ in ascending order.
- We initialize ‘carry’ to 0.
- We traverse DIGITS from end to start to add digits at the ones place first followed by tens, hundreds and so on.
- We alternatively choose the digits to get the two numbers (for example, choosing DIGITS[i] for the first number and DIGITS[i-1] for the second or vice-versa).
- We calculate the sum of the two digits, find the carry and store sum of digits in the ‘password’ vector/list.
- We remove leading zeros, if any, and reverse ‘password’.
- Finally, we return ‘password’ as our answer.
The main idea behind this approach is that since ‘DIGITS’ contains values only from 0-9, we can store their count instead of sorting the entire array.
Here is the complete algorithm:
- We maintain a ‘count’ array of size 10 initialized to 0.
- We traverse ‘DIGITS’ and store the count of each element.
- Now, we traverse ‘count’ from beginning to end.
- We store digit ‘i’ count[i] times in DIGITS. This sorts the array in linear time.
- We then calculate the sum of two numbers digit by digit and store the sum in the ‘password’ array as discussed in the previous approach.
- Finally, we return ‘password’ as our answer.