Jumping Number is a number in which all the adjacent digits of a number differ by one. For example, the number 7898 is considered a jumping number. But the number 468 is not. All uni digits are considered jumping numbers.

Now the question arises if given a number x, print all the jumping numbers smaller than or equal to x. We can print the numbers in any order.

For this naive approach, the time complexity will be O(N).

Space Complexity

For this naive approach, the space complexity will be O(1).

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Efficient Approach

We can solve this problem using BFS/DFS Algorithm, according to oneâ€™s efficiency in both methods. It takes a time of O(K), where k is the number of jumping numbers less than or equal to x.

Algorithm

đź‘‰Iterate from 1 to min(x,9).

đź‘‰During each iteration, pass each digit(1-min(x,9)) and the number x into the bfs function.

đź‘‰Push the digit and the number into a queue.

đź‘‰Add digits with an absolute difference of one with the previous digit to the current number.

đź‘‰Check if the newly formed number is less than x or not. If yes, push it into the queue or else continue.

Lets take a example for input x = 100

Initial node = 0
From 0, we can move to nine different points,i.e., 1 2 3 4 5 6 7 8 9.

Now,

From 1, we can jump to 12 and 10.
From 2, we can jump to 23 and 21.
From 3, we can jump to 34 and 32.
.
.
And so on.

Now letâ€™s move to the coding part. You will have a better understanding after I walk you through the code.

C++ Code

#include <bits/stdc++.h>
using namespace std;
void bfs(int x, int num)
{
queue<int> q;
q.push(num);
/* Do BFS starting from i */
while (!q.empty()) {
num = q.front();
q.pop();
if (num <= x) {
cout << num << " ";
int prev_digit = num % 10;
/* If the last digit is zero, append the next digit only */
if (prev_digit == 0)
q.push((num * 10) + (prev_digit + 1));
/* If the last digit is nine, append the previous digit only */
else if (prev_digit == 9)
q.push((num * 10) + (prev_digit - 1));
/* If the last digit is neither zero nor nine, append both previous and next digits */
else {
q.push((num * 10) + (prev_digit - 1));
q.push((num * 10) + (prev_digit + 1));
}
}
}
}
// Driver program
int main()
{
int x;
//Taking input number.
cin>>x;
cout << 0 << " ";
for (int i = 1; i <= 9 && i <= x; i++)
bfs(x, i);
return 0;
}

Python Code

# Class queue for use later
class Queue:
def __init__(self):
self.lst = []
def is_empty(self):
return self.lst == []
def enqueue(self, elem):
self.lst.append(elem)
def dequeue(self):
return self.lst.pop(0)
def bfs(x, num):
# Create a queue and enqueue i to it
q = Queue()
q.enqueue(num)
# Do BFS starting from 1
while (not q.is_empty()):
num = q.dequeue()
if num<= x:
print(str(num), end =' ')
prev_digit = num % 10
# If the last digit is zero, append the next digit only
if prev_digit == 0:
q.enqueue((num * 10) + (prev_digit + 1))
# If the last digit is nine, append the previous digit only
elif prev_digit == 9:
q.enqueue((num * 10) + (prev_digit - 1))
# If the last digit is neither zero nor nine, append
# both previous digit and next digit
else:
q.enqueue((num * 10) + (prev_digit - 1))
q.enqueue((num * 10) + (prev_digit + 1))
def print(x):
print (str(0), end =' ')
for i in range(1, 10):
bfs(x, i)
# Driver Program
x = 50
print(x)

Output

Time Complexity

It takes a time of O(K), where k is the number of jumping numbers less than or equal to x.

Space Complexity

It takes a space of O(1).

Frequently Asked Questions

What are jumping numbers?

Jumping Number is a number in which all the adjacent digits of a number differ by one. For example, the number 7898 is considered a jumping number. But the number 468 is not. All uni digits are considered jumping numbers.

Which algorithm is used to find the jumping number for some x?

BFS/DFS is used to find the jumping number for a number x.

What is the space complexity for the bfs approach?

The space complexity is O(K), where k is a constant.

What is the time complexity for bfs approach?

The time complexity for the bfs approach is O(K), where k is the number of jumping numbers less than or equal to x.

Are all the single-digit numbers jumping numbers?

Yes, all single-digit numbers from 0 to 9 are considered jumping numbers.

Firstly, we saw the meaning of jumping numbers with the help of an example. Further, we discussed the naive and efficient approaches and their complexities. Thatâ€™s the end of the article. I hope you all like this article.

You can practice these questions here to brush up on your knowledge.