Last Updated: 4 Jan, 2021
Jumping Numbers
Moderate
Asked in companies
You are given a positive integer N, your task is to find all the Jumping Numbers smaller than or equal to N.
A number is defined as a Jumping Number if all adjacent digits in it have an absolute difference of 1.
Example :
2, 23, and 4343456 are Jumping numbers but 296 and 89498 are not.
Note:
The difference between ‘9’ and ‘0’ is not considered as 1. All single-digit numbers are considered as Jumping Numbers.
Input Format:
The first line contains an integer 'T' denoting the number of test cases.
The only line of each test case contains an integer N.
Output Format:
For each test case, print all the Jumping Numbers smaller than or equal to N in ascending order.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^8
Time Limit: 1 sec
Approaches
This is the basic solution to this problem.
- Traverse all numbers from 0 to N.
- For every traversed number, check if it is a Jumping Number or not.
- To check if a number is jumping or not, we’ll make a boolean function named check(), which will return true if the number is a jumping number.
- Inside this check function, we’ll first extract all the digits of the number and store it in an array.
- Then we check whether the absolute difference in the adjacent digits is 1 or not.
- If we encounter any two adjacent digits whose absolute difference is not 1, we return false. Else we return true.
- Inside our jumpingNumber() function we traverse all the numbers from 1 to N and call the check function to see whether the current number is a jumping number or not.
- If it is a jumping number, print it and move further to the next number.
- If this number is not a jumping number, then ignore it and move to the next number.
- This approach is very efficient as we won't be traversing all the numbers from 0 to N. Here we’ll be using the concept of Breadth-First Search using a FIFO queue. Assume that we have a graph where the starting node is 0. From that node, we go to whichever next node is possible using Breadth-First Search(we can also use Depth First Search). We’ll continue this till the numbers are less than N if they become greater than N, we stop. Let us understand how we’ll implement this.
- We create our function jumpingNumbers() inside which will be similar to a bfs function.
- Inside this, we’ll create a queue and we will then enqueue the iterator(i) to it(let’s name it num), i.e we’ll push num into this queue.
- Now we run a loop till this queue becomes empty.
- We assign the front value to the queue to this “num” and then pop this value from the queue.
- Now we check if num is less than N or not. Only if this condition is true we move further.
- We print this num value and then push in all the values which we can reach from this num value. We do this by making the following cases.
- If the last digit of num is 0, then we push the value of num+(last digit + 1), as we cannot decrease our unit digit’s place more than 0.
- If the last digit of num is 9, then we push the value of num+(last digit - 1), as we cannot increase our unit digit’s place more than 9.
- For all other cases, we both push both num+(last digit + 1) and num+(last digit - 1), as we can decrease and increase the unit digit’s place by 1.
Finally, as the output needs to be in ascending order, we sort our array accordingly
For example, let’s take N = 20.
- Our first step will be to print 0.
- Then we start with 1 and print all integers till 9.
- From 1 we can go to 0 and 2, hence we print 10 and 12.
- Then we go to 2 and print 2 and similarly print 21 and 23.
- Now we go to 3, we print 3. Now we see that from 3 we can go to 2 and 4 but this will result in violating our condition, as both of these combinations will be 32 and 34 which is greater than 20, hence we’ll not print them.
- Our final answer will be 0 1 2 3 4 5 6 7 8 9 10 12 21 23