Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Naive Approach
2.1.
Algorithm
2.2.
C++ Code
2.2.1.
Output
2.2.2.
Time Complexity
2.2.3.
Space Complexity
3.
Efficient Approach
3.1.
Algorithm
3.2.
C++ Code
3.3.
Python Code
3.3.1.
Output
3.3.2.
Time Complexity
3.3.3.
Space Complexity
4.
Frequently Asked Questions
4.1.
What are jumping numbers?
4.2.
Which algorithm is used to find the jumping number for some x?
4.3.
What is the space complexity for the bfs approach?
4.4.
What is the time complexity for bfs approach?
4.5.
Are all the single-digit numbers jumping numbers?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Jumping Numbers Smaller Than or Equal to a Given Value

Author Mayank Goyal
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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 example:

Input n: 25

Output: 0 1 2 3 4 5 6 7 8 9 10 12 21 23

Input x: 50

Output: 0 1 2 3 4 5 6 7 8 9 10 12 21 23 32 34 43 45

Naive Approach

Algorithm

👉Iterate over all the numbers from zero to x.

👉For every traversed number, check whether it's jumping or not.

👉If yes, store it in a vector.

C++ Code

#include <bits/stdc++.h>

using namespace std;

void solve(int& x)
{
 int i,temp,digit;
 bool check;
 
 for(i=0;i<=x;i++)
 {
  if(i<10)
  {
   cout<<i<<" ";
   continue;
  }
  check=1;
  temp=i;
  digit=temp%10;
  temp/=10;
  while(temp)
  {
   if(abs(digit-temp%10)!=1)
   {
    check=0;
    break;
   }
   digit=temp%10;
   temp/=10;
  }
  if(check)
  cout<<i<<" ";
 }
}

int main()
{
 int x=100;
 solve(x);

 return 0;
}

Output

output

Time Complexity

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.

graph

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

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 TraversalRegular and Bipartite graphsWhat Is Web2Py?Why To Use Web2py?Postbacks and Internationalization in web2pyThird Party Modules In Web2pyTasks In Web2py, and  XML in Web2py.

Happy Coding!

Previous article
The Stable Marriage Problem
Next article
STL-based BFS for competitive coding
Live masterclass