Jumping Numbers

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
94 upvotes
Asked in companies
OperaOracleGoogle

Problem statement

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. 
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
20
Sample Output 1:
0 1 2 3 4 5 6 7 8 9 10 12
Explanation For Sample Input 1:
These are all the jumping numbers from 0 to 12 as all the single-digit numbers are jumping numbers and out of the two-digit numbers only 10 and 12 are the jumping numbers less than 20 as the absolute difference in the adjacent digits of 10 and 12 is 1.
Sample Input 2:
2
1
30
Sample Output 2:
0 1
0 1 2 3 4 5 6 7 8 9 10 12 21 23 
Hint

Brute Force

Approaches (2)
Brute Force Approach

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.
Time Complexity

O(N), where N is the number till which we have to find all the jumping numbers.

 

While traversing numbers from 0 to N, we’re checking if the current number is a jumping number or not. Hence for each operation, it takes O(1) Time and as we’re checking each integer from 0 to N, it’ll take O(N) time.

Space Complexity

O(1)

 

As we are using constant extra memory.

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Jumping Numbers
Full screen
Console