Last Updated: 10 Sep, 2020

Nth Number

Hard

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

The Idea is to use binary search to find the Nth Number with a digit sum equal to 10. For this to calculate, we will do a binary search in the possible range(1 to MAX) where MAX denotes the Maximum number possible(LONG_MAXVALUE). For each MID value, we will find the count of numbers less than or equals MIN with digit sum equals 10. If the count equals N we will mark the MID value as the answer and check for the left part of our search to find the exact Nth number. Similarly, if the count is greater than N we need to decrease the possible range (search to the left side). Otherwise, if the count is smaller than N, we will move to the right part of our search to include more such numbers.

Now, to find all numbers less than a particular number say X, with digit sum 10, we iterate the number by replacing its digits such that it is less than X. If this number satisfies the property, increment the count. To iterate the number we will start from the Most Significant Bit and set all possible bits at this place and call for the next most significant bit.

Forex, lets say X = 485.

Now Most significant bit = 4 to iterate over all possible numbers we will set SMALLER = 1 which will tell us that the limit of the current bit equals the value of that bit in X. So we can choose the most significant bits as 0,1,2,3 and while choosing 4 we will update limit. Similarly, we can keep iterating on the next bits.

Given below is the pseudocode on how we will calculate this recursively.

Pseudocode:

X[1...Len] // X is the number with Len number of digits.

// smaller(initially 1) is a flag to determine the limit of the next digit in the sequence such that the value remains < X.
int count(index, smaller, digitsum)
    // We have build a number less than X with Len digits
if index = Len
if digitsum = 10
return 1
return 0

    //
if smaller = 1
limit = X[index]
else
limit = 9

for d = 0 to limit
if d < X[index]
ans = ans + count(index + 1, 0, digitsum + d)
else
ans = ans + count(index + 1, smaller, digitsum + d)

return ans

Note: This approach will always give TLE even for small numbers. As in the binary search we have chosen large numbers(LONG_MAX) due to uncertainty for the Nth number.

Solve now

03 Approach

The Idea is to use binary search to find the Nth Number with a digit sum equal to 10. For this to calculate, we will do a binary search in the possible range(1 to MAX) where MAX denotes the Maximum number possible(LONG_MAXVALUE). For each MID value, we will find the count of numbers less than or equals to MIN with digit sum equals to 10. If the count equals N we will mark the MID value as the answer and check for the left part of our search to find the exact Nth number. Similarly, if the count is greater than N we need to decrease the possible range( search to the left side). Otherwise, if the count is smaller than N, we will move to the right part of our search to include more such numbers.

Now, to find all numbers less than a particular number say X, with digit sum 10. As we iterated on all numbers using recursion. Here we will use memoization to avoid calculating repeated subproblems. The idea is similar to digit dp as discussed![here](https://codeforces.com/blog/entry/53960)

Pseudocode:

X[1...Len] // X is the number with Len number of digits.
dp[Len][2][11] // to store the calculations

// smaller(initially 1) is a flag to determine the limit of the next digit in the sequence such that the value remains < X.
int count(index, smaller, digitsum)
if index = N
if digitsum = 10
return 1
return 0

    if dp[index][smaller][digitsum] != 1
        return dp[index][smaller][digitsum]

if smaller = 1
limit = X[index]
else
limit = 9

for d = 0 to limit
if d < X[index]
ans = ans + count(index + 1, 0, digitsum + d)
else
ans = ans + count(index + 1, smaller, digitsum + d)

return dp[index][smaller][digitsum] = ans

Solve now