[Geeks for Geeks] Jumping Numbers

Jumping Numbers

Given a positive number X. Find the largest Jumping Number smaller than or equal to X.
Jumping Number: A number is called Jumping Number if all adjacent digits in it differ by only 1. All single digit numbers are considered as Jumping Numbers. For example 7, 8987 and 4343456 are Jumping numbers but 796 and 89098 are not.

  • Time : O(logX)
  • Space : O(logX)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
long long helper(long long X, long long pos, long long now, long long prev) {
if(pos == -1) return now;
long long mod = pow(10, pos);
long long res = -1;
if(prev != 9) {
long long upper = mod * (prev + 1);
long long nxt = now + upper;
if(nxt <= X) {
res = max(res, helper(X, pos - 1, nxt, prev + 1));
}
}
if(prev != 0 and res == -1) {
long long lower = mod * (prev - 1);
long long nxt = now + lower;
if(nxt <= X) {
res = max(res, helper(X, pos - 1, nxt, prev - 1));
}
}
return res;
}
public:
long long jumpingNums(long long X) {
if(X <= 10) return X;
long long digits = log10(X);
long long mod = pow(10,digits);
if((X / mod) - 1 == 0) {
return max(helper(X, digits - 1, X / mod * mod, X / mod), helper(X, digits - 2, 9 * mod / 10, 9));
}
return max(helper(X, digits - 1, X / mod * mod, X / mod), helper(X, digits - 1, ((X / mod) - 1) * mod, (X / mod) - 1));
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/17/PS/GeeksforGeeks/jumping-numbers/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.