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:

25

Sample Output:

0 1 2 3 4 5 6 7 8 9 10 12 21 23

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

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.