Jumping Numbers Smaller Than or Equal to a Given Value

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.

You can also try this code with Online C++ Compiler

Run Code

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.

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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.

You can also read about - Strong number in c

Conclusion

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.

If you want to learn more, check out our articles on Construct the Full K-ary Tree from its Preorder Traversal, Regular and Bipartite graphs, What Is Web2Py?, Why To Use Web2py?, Postbacks and Internationalization in web2py, Third Party Modules In Web2py, Tasks In Web2py, and  XML in Web2py.

Happy Coding!