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

Google cancels our Google Play publisher account and ends my family’s source of income

deleted google play account

Configuring ELK stack in winodws.

Introducing the Accessibility Inspector in the Firefox Developer Tools

Reduce Developer Workload using codeless Microservice Technology — Part 1

Enigma — Development Log #2

How I Turned Forced Remote Coding Into True Smart Working

Experiencing smart working at the beginning was overwhelming

How My Team Implemented Agile Software Development Using Scrum

Find Duplicate in Array

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

Class Quiz

PlatinumX Tech’s Algorithm Expert Course Review (How I got into Turing).

Leetcode 862. Shortest Subarray with Sum at Least K

Reorder Data in Log Files