Good Numbers

Easy

0/40

Average time to solve is 20m

Contributed by

71 upvotes

Asked in companies

Problem statement

A number is called good if it's every digit (except the rightmost digit) is larger than the sum of digits on the right side of that digit.

Find all the good numbers in the range from 'a' to 'b' (both inclusive), such that none of them contains 'digit' as a digit.

Example :

Input: 'a' = 840, 'b' = 850 and 'digit' = 6

Output: Good numbers = [840, 841, 842, 843, 850]

Explanation: Consider 841:
8 > (4 + 1)
4 > 1
Since each digit is greater than the sum of digits on right (except 1, which does not have any digit on its right), 841 is a good number. Similarly, all these numbers are good.

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

Input Format :

The first line contains two integers 'a' and 'b', denoting the range.
The second line contains an integer 'digit', the digit which should not be there in the good numbers.

Output Format :

Print all the good numbers in the range from 'a' to 'b' such that none of them have 'digit'.

Note :

You do not need to print anything; it has already been taken care of. Just return the list of good numbers in any order. It will be sorted in ascending order and printed.

Sample Input 1:

840 850
6

Sample Output 1:

840 841 842 843 850

Explanation of sample input 1 :

Consider 841:
8 > (4 + 1)
4 > 1
Since each digit is greater than the sum of digits on right (except 1, which does not have any digit on its right), 841 is a good number. Similarly, all these numbers are good.

Sample Input 2:

20 45
1

Sample Output 2:

20 30 32 40 42 43

Explanation of sample input 2 :

The good numbers in this range are:
20 21 30 31 32 40 41 42 43

Among these, 21, 31 and 41 have digit 1 in them, so they are not included.

Expected time complexity :

The expected time complexity is O(b * log(b) - a * log(a)).

Constraints :

1 <= 'a' <= 'b' <= 10000
0 <= 'digit' <= 9

Time limit: 1 second

Console