# 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:

Sample Output:

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

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