Welcome to Subscribe On Youtube
3753. Total Waviness of Numbers in Range II
Description
You are given two integers num1 and num2 representing an inclusive range [num1, num2].
The waviness of a number is defined as the total count of its peaks and valleys:
- A digit is a peak if it is strictly greater than both of its immediate neighbors.
- A digit is a valley if it is strictly less than both of its immediate neighbors.
- The first and last digits of a number cannot be peaks or valleys.
- Any number with fewer than 3 digits has a waviness of 0.
Return the total sum of waviness for all numbers in the range [num1, num2].
Example 1:
Input: num1 = 120, num2 = 130
Output: 3
Explanation:
In the range [120, 130]:
120: middle digit 2 is a peak, waviness = 1.121: middle digit 2 is a peak, waviness = 1.130: middle digit 3 is a peak, waviness = 1.- All other numbers in the range have a waviness of 0.
Thus, total waviness is 1 + 1 + 1 = 3.
Example 2:
Input: num1 = 198, num2 = 202
Output: 3
Explanation:
In the range [198, 202]:
198: middle digit 9 is a peak, waviness = 1.201: middle digit 0 is a valley, waviness = 1.202: middle digit 0 is a valley, waviness = 1.- All other numbers in the range have a waviness of 0.
Thus, total waviness is 1 + 1 + 1 = 3.
Example 3:
Input: num1 = 4848, num2 = 4848
Output: 2
Explanation:
Number 4848: the second digit 8 is a peak, and the third digit 4 is a valley, giving a waviness of 2.
Constraints:
1 <= num1 <= num2 <= 1015
Solutions
Solution 1
-
static int len, digits[20]; static long long memoCnt[20][11][11][2]; static long long memoSum[20][11][11][2]; static char vis[20][11][11][2]; static long long cnt, sum; static void dfs(int pos, int pp, int pr, int st, int ti) { if (pos == len) { cnt = 1; sum = 0; return; } if (!ti && vis[pos][pp][pr][st]) { cnt = memoCnt[pos][pp][pr][st]; sum = memoSum[pos][pp][pr][st]; return; } int h = ti ? digits[pos] : 9; long long c = 0, s = 0; for (int d = 0; d <= h; d++) { int ns = st || d; long long a = 0; int npp, np; if (!ns) { npp = 10; np = 10; } else if (!st) { npp = 10; np = d; } else { if (pp != 10 && pr != 10 && ((pr > pp && pr > d) || (pr < pp && pr < d))) a = 1; npp = pr; np = d; } dfs(pos + 1, npp, np, ns, ti && d == h); c += cnt; s += sum + a * cnt; } if (!ti) { vis[pos][pp][pr][st] = 1; memoCnt[pos][pp][pr][st] = c; memoSum[pos][pp][pr][st] = s; } cnt = c; sum = s; } static long long calc(long long N) { if (N < 0) return 0; len = 0; long long x = N; if (!x) { digits[len++] = 0; } else { char buf[20]; int l = 0; while (x) { buf[l++] = x % 10; x /= 10; } for (int i = l - 1; i >= 0; i--) digits[len++] = buf[i]; } memset(vis, 0, sizeof(vis)); dfs(0, 10, 10, 0, 1); return sum; } long long totalWaviness(long long a, long long b) { return calc(b) - calc(a - 1); }