Closest greater

Easy

0/40

Average time to solve is 15m

Contributed by

5 upvotes

Asked in company

Problem statement

Given a positive integer ‘N’, you have to find the closest number to 'N' which is greater than ‘N’, and has at most one non-zero digit. In other words, you have to find a number ‘K’ such that:

1. 'K' should be strictly greater than 'N'.

2. 'K' should contain at most 1 non-zero digit. 

3. Difference between 'N' and 'K' should be minimum.

For eg.

Consider the number 546. The closest number greater than 546 that contains at most 1 non-zero digit is 600.

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

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and the only line of each test case contains a positive integer ‘N’.

Output Format

For each test case, print a single line containing a single integer denoting the number 'K' as described above in a single line. 

The output for each test case will be printed in a separate line.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 1000
1 <= N <= 10 ^ 18

Time limit: 1 second

Sample Input 1:

2
13 
100

Sample Output 1:

20
200

Explanation of sample input 1:

Test case 1:
We can see that the numbers greater than 13, having at most one non-zero digit are 20, 30, 40, 50... so on. The answer is 20 because it is the closest to 13. 

Test case 2:
Clearly, the first greater number than 100 containing at most one non-zero digit is 200.

Sample Input 2:

2
999 
30001

Sample Output 2:

1000
40000

Hint 1

Try to observe the mathematical pattern.

Approaches (1)

Approach 1

Observation

If we see the pattern, we can see that we just have to increment the first digit by one and replace the rest of the digits by zero.

For example:

N = 65, Answer = 70
N = 999, Answer = 1000

Algorithm:

Initialise a variable ‘count’ that will store the number of digits of ‘N’.
Store the first digit of ‘N’ in a variable ‘firstDigit’.
Initialise the output variable ‘result’ as firstDigit + 1;
Run a loop ‘count’ - 1 time and keep adding 0 to the ‘result’, i.e keep multiplying ‘result’ by 10.
Return the ‘result’.

Time Complexity

O(log10N), where ‘N’ is the given number.

We are just running a loop ‘count’-1 times where ‘count’ is the number of digits. Hence the time complexity is O(‘count’) or O(log10N).

Space Complexity

O(1).

Since we are not using any extra space. We are just taking a variable which is constant space.

(100% EXP penalty)

Closest greater

Console