Jumping Numbers — Asked in Google, Amazon and Oracle Interview

Problem Statement :

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 :

Approach :

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

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

Upskilling students for tech placements!