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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

From Funk to Functions

From Start to Finish Part 1

How Do SMEs Efficiently Develop Software at Home

How to install Impacket tools in any linux

Apache Kafka Security with Kerberos on Kubernetes

Connection Pooling — what and why?

Connect to google drive from colab notebook- in one step

Seizing the Opportunity in the New Cloud Native Battlefield

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

543. Diameter of Binary Tree

Leetcode 701. Insert into a Binary Search Tree

Leetcode 820. Short Encoding of Words

LeetCode 146. LRU Cache