Find the password

Easy
0/40
Average time to solve is 10m
profile
Contributed by
2 upvotes

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 2 9 8
3
1 1 0
Sample Output 1 :
47
2

Sample Output 1 Explanation:

For the first test case, the password  is 47 which is the minimum sum obtained by adding numbers 18 and 29.

For the second test case, the password is 12 which is the minimum sum obtained by adding numbers 01 and 1.
Sample Input 2 :
1
2
2 8
Sample Output 2 :
10
Hint

Think of rearranging the DIGITS in a way that helps in finding those two numbers easily.

Approaches (2)
Sorting the digits

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 - 

  1. We will sort the ‘DIGITS’ in ascending order.
  2. We initialize ‘carry’ to 0.
  3. We traverse DIGITS from end to start to add digits at the ones place first followed by tens, hundreds and so on.
    1. 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).
    2. We calculate the sum of the two digits, find the carry and store sum of digits in the ‘password’ vector/list.
  4. We remove leading zeros, if any, and reverse ‘password’.
  5. Finally, we return ‘password’ as our answer.
Time Complexity

O(NlogN), where N denotes the number of digits provided.

 

Sorting the digits takes O(NlogN) time. We then traverse all digits to find the two numbers and calculate their sum which takes O(N) time. Thus, the overall time complexity is O(NlogN).

Space Complexity

O(1), constant space is used.

Code Solution
(100% EXP penalty)
Find the password
Full screen
Console