Problem

Submissions

Hints & solutions

Discuss

Jumping Numbers

Hard

0/120

Average time to solve is 10m

Contributed by

20 upvotes

Asked in companies

Problem statement

You are given a positive integer 'N'. Your task is to print all the jumping numbers smaller than or equal to 'N'.

A number is called a jumping number if all adjacent digits in it differ by 1. All the single-digit numbers are considered jumping numbers.

Note:

The difference between ‘9’ and ‘0’ is not considered as 1.

Example:

Let’s say 'N' = 25. The jumping numbers less than or equal to 25 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23. In all these numbers the adjacent digits differ by 1.

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

Input Format:

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

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

Output Format:

For each test case, print a single line containing less than or equal to 'N' integers representing all the jumping numbers in sorted order.

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^8

Time Limit: 1 sec

Sample Input 1:

2
25
45

Sample Output 1:

0 1 2 3 4 5 6 7 8 9 10 12 21 23
0 1 2 3 4 5 6 7 8 9 10 12 21 23 32 34 43 45

Explanation 1:

For the first test case, refer to the example explained before.

For the second test case, N = 45. The jumping numbers less than 25 are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, 43, 45.

Sample Input 2:

2
10
1

Sample Output 2:

0 1 2 3 4 5 6 7 8 9 10
0 1

Hint 1

Hint 2

Hint 3

Can you solve this problem by checking all the numbers from 0 to N?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

A brute force approach could be to iterate over all the integers from 0 to N.
For each integer check if its adjacent digits differ by 1. If yes, then the number is a jumping number.

The steps are as follows:

Iterate over the integers, 0 to ‘N’.
For each integer, iterate over its digits.
- Check if the current digit and the previous digit differ by 1.
If all the adjacent digits in the current integer differ by 1, add the integer to the list of jumping numbers.

Time Complexity

O(N), where ‘N’ is the given positive integer.

In the worst case, we are iterating over all the integers from 0 to ‘N’ which requires O(N) time. Also, checking the difference between adjacent digits, for each number requires approximately constant time. Hence, the overall time complexity is O(N).

Space Complexity

O(1).

Constant extra space is required.

(100% EXP penalty)

Jumping Numbers

Console