Nth Number

Hard

0/120

Average time to solve is 50m

17 upvotes

Asked in companies

Problem statement

In a series of numbers where each number is such that the sum of its digits equals 10. Given an integer value 'N', your task is to find the N-th positive integer whose sum of digits equals to 10.

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

Input Format:

The first line contains an Integer 'T' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first line of input for each test case/query contains an integer N, the Nth number to find.

Output Format:

For each test case, print the N-th positive integer whose sum of digits equals 10.

Output for every test case will be printed in a separate line.

Note

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^7    

Time Limit: 1sec

Sample Input 1:

2
1
4

Sample Output 1:

19
46

Explanation of Sample Input 1:

Since N=1 here, therefore, the first number having a sum of digits equal to 10 is 19. Therefore, the output here is 19.

Since N=4 here, therefore, The first four numbers having a sum of digits equal to 10 are 19, 28, 37, and 46. Therefore, the output here becomes 46.

Sample Input 2:

2
5
9

Sample Output 2:

55
91

Hint 1

Hint 2

Hint 3

Iterate over all numbers until we find the n-th number with a digit sum equals to 10.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The brute force approach is to iterate through numbers starting from 1. For each number, we will check its digit sum. If the digit sum equals 10 we will increment the count. When the count becomes equal to N we will return the current number.

Time Complexity

O(X), where X is the Nth Number with a digit sum equals to 10.

In the worst case, we will be iterating on all numbers from 1 to X.

Space Complexity

O(1), In the worst case, only a constant extra space is required.

(75% EXP penalty)

(100% EXP penalty)

Nth Number

Console