Smallest Unique Digit Sum

Moderate

0/80

0 upvote

Asked in companies

Problem statement

You are given an integer N. Your task is to construct the smallest possible positive integer that satisfies two conditions:

1) The sum of its digits is exactly N.
2) All of its digits are unique (digits from 1 to 9 can be used at most once).

If it's impossible to form such a number, you should return -1.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

A single line containing the integer N.

Output Format:

Print a single integer representing the smallest number that meets the criteria.
If no such number can be formed, print -1.

Note:

To make the resulting number as small as possible, it should have the fewest digits. To achieve the sum N with the fewest unique digits, we should greedily pick the largest available digits (9, then 8, then 7, and so on).

Once we have the set of digits that sum to N, we must arrange them in ascending order to form the smallest possible number.

The sum of all unique digits from 1 to 9 is 1+2+...+9 = 45. If N is greater than 45, it is impossible to form the number, so the answer must be -1.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

To get a sum of 15 using the largest unique digits:
1.  Pick 9. The remaining sum needed is `15 - 9 = 6`.
2.  Pick the next largest available digit that is not greater than 6, which is 6. The remaining sum is `6 - 6 = 0`.
The digits we chose are `{9, 6}`. To form the smallest number, we arrange them in ascending order: `69`.

Sample Input 2:

Sample Output 2:

-1

Explanation for Sample 2:

The maximum possible sum using unique digits from 1 to 9 is 45. Since N=50 is greater than 45, it is impossible to form the required number.

Expected Time Complexity:

The expected time complexity is O(1), as the process involves a loop that runs at most 9 times.

Constraints:

1 <= N <= 50

Time limit: 1 sec

Approaches (1)

Approach 1

Smallest Unique Digit Sum

Time Complexity

Space Complexity

(100% EXP penalty)

Smallest Unique Digit Sum

Console