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