Jumping Numbers — Asked in Google, Amazon and Oracle Interview
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.
Sample Input:
25Sample Output:
0 1 2 3 4 5 6 7 8 9 10 12 21 23Explanation of given Test Cases :
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.
Approach :
Using BFS To Generate Jumping Numbers
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.
Time complexity: O(K*logK)
Space Complexity: O(K)
Where K is the number of jumping numbers smaller than or equal
to given positive integer N.
