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 )); } };