Problem of the day
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.
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.
1 <= T <= 100
1 <= N <= 10^8
Time Limit: 1 sec
1
20
0 1 2 3 4 5 6 7 8 9 10 12
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.
2
1
30
0 1
0 1 2 3 4 5 6 7 8 9 10 12 21 23
Brute Force
This is the basic solution to this problem.
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.
O(1)
As we are using constant extra memory.