Jumping Numbers
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.

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

Question

Jumping Numbers

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.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1).

Constant extra space is required.

Time Complexity: O(n)Explanation:

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).

Accepted Answer

Using DFS To Generate Jumping Numbers

Instead of checking every integer, we can directly generate the jumping numbers.
In order to do so, we start with the first jumping number i.e. 0. And append a new digit to it such that the difference between the next digit and the previous digit is 1. For ‘0’ as the previous digit, the only possible next digit is 1, this gives us the next jumping number i.e. 01 or 1.
We repeat the same procedure with 1. But here we have two possible options for the next digit i.e. ‘2’ and ‘0’. This generates two new jumping numbers: 12 and 10.
An important point to note here is that in case the last digit of the number is 0 then the only possible option for the next digit is 1. Similarly, for 9 the only possible next digit is 8. But for the numbers 1 to 8, we’ll always have two options for the next digits (one less and the other greater than it).

The steps are as follows:

The above approach can be implemented by assuming the numbers as the nodes of the graph.
Starting with node ‘0’, apply DFS on the graph.
Base Condition: If the node/number generated is greater than N, we stop the traversal for that node and return.
Since, the number is less than N, add the current node/number to the list of jumping numbers.
Now, to transit from one node to the next, append digits to the current node such that the next number generated is also a jumping number (as described previously) and then recursively call DFS on the next node.
In order to generate all the jumping numbers, repeat the above algorithm by taking the remaining integers 2-9 as the starting nodes.
Now, sort the list of jumping numbers and return it.

Space Complexity: O(n)Explanation:

O(K), where ‘K’ is the number of jumping numbers smaller than or equal to ‘N’.

In the worst case, O(K) extra space is required for the recursion stack in DFS.

Time Complexity: O(nlogn)Explanation:

O(K*log(K)), where ‘K’ is the number of jumping numbers smaller than or equal to ‘N’.

In the worst case, we will be traversing ‘K’ nodes of the graph, where each node represents a jumping number less than or equal to ‘N’. Sorting the list of jumping numbers requires O(K*log(K)) time. Hence, the overall time complexity is O(K) + O(K*log(K)) = O(K*log(K)). For large values of ‘N’, ‘K’<<'N', so this approach is faster than O(N).

Accepted Answer

Using BFS To Generate Jumping Numbers

This approach is similar to the previous one but instead of using DFS, we can use BFS to generate the graph.

The steps are as follows:

Initialize an empty queue and push the starting node i.e. ‘0’ in it.
Repeat the following steps until the queue becomes empty:
- Pop the top node from the queue. This will be the current node which we are exploring.
- If the current node/number is less than or equal to ‘N’, then add it to the list of jumping numbers.
- And generate the next node by appending digits to the current node such that the next number/node generated is also a jumping number. And push it into the queue.
- Otherwise, move to the next node in the queue.
In order to generate all the jumping numbers, repeat the above algorithm by taking the remaining integers 2-9 as the starting nodes.
Now, sort the list of jumping numbers and return it.

Space Complexity: O(n)Explanation:

O(K), where ‘K’ is the number of jumping numbers smaller than or equal to ‘N'.

In the worst case, O(K) extra space is required for the queue.

Time Complexity: O(nlogn)Explanation:

O(K*log(K)), where ‘K’ is the number of jumping numbers smaller than or equal to ‘N’.

In the worst case, we will be traversing ‘K’ nodes of the graph, where each node represents a jumping number less than or equal to ‘N’. Sorting the list of jumping numbers requires O(K*log(K)) time. Hence, the overall time complexity is O(K) + O(K*log(K)) = O(K*log(K)). For large values of ‘N’, ‘K’<<'N', so this approach is faster than O(N).

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:

Example:

Input Format:

Output Format:

Note:

Constraints:

Top Red Hat Software Developer interview questions & answers

Popular interview questions of Software Developer