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); } -
class Solution { private char[] cs; private long[][][][] cnt; private long[][][][] wav; public long totalWaviness(long num1, long num2) { return calc(num2) - calc(num1 - 1); } private long calc(long x) { if (x < 0) { return 0; } cs = Long.toString(x).toCharArray(); int n = cs.length; cnt = new long[n][11][11][2]; wav = new long[n][11][11][2]; for (int i = 0; i < n; ++i) { for (int a = 0; a < 11; ++a) { for (int b = 0; b < 11; ++b) { Arrays.fill(cnt[i][a][b], -1); Arrays.fill(wav[i][a][b], -1); } } } return dfs(0, 10, 10, 0, true)[1]; } private long[] dfs(int pos, int prev2, int prev1, int started, boolean limit) { if (pos == cs.length) { return new long[] {started, 0}; } if (!limit && cnt[pos][prev2][prev1][started] != -1) { return new long[] {cnt[pos][prev2][prev1][started], wav[pos][prev2][prev1][started]}; } int up = limit ? cs[pos] - '0' : 9; long c = 0, w = 0; for (int d = 0; d <= up; ++d) { boolean nlimit = limit && d == up; int ns, np2, np1, add = 0; if (started == 0) { if (d == 0) { ns = 0; np2 = 10; np1 = 10; } else { ns = 1; np2 = 10; np1 = d; } } else { ns = 1; np2 = prev1; np1 = d; if (prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d))) { add = 1; } } long[] t = dfs(pos + 1, np2, np1, ns, nlimit); c += t[0]; w += t[1] + t[0] * add; } if (!limit) { cnt[pos][prev2][prev1][started] = c; wav[pos][prev2][prev1][started] = w; } return new long[] {c, w}; } } -
class Solution { public: long long totalWaviness(long long num1, long long num2) { return calc(num2) - calc(num1 - 1); } private: string s; long long fCnt[20][11][11][2]; long long fWav[20][11][11][2]; bool vis[20][11][11][2]; long long calc(long long x) { if (x < 0) { return 0; } s = to_string(x); memset(vis, 0, sizeof(vis)); return dfs(0, 10, 10, 0, true).second; } pair<long long, long long> dfs(int pos, int prev2, int prev1, int started, bool limit) { if (pos == s.size()) { return {started, 0}; } if (!limit && vis[pos][prev2][prev1][started]) { return {fCnt[pos][prev2][prev1][started], fWav[pos][prev2][prev1][started]}; } int up = limit ? s[pos] - '0' : 9; long long c = 0, w = 0; for (int d = 0; d <= up; ++d) { bool nlimit = limit && d == up; int ns, np2, np1, add = 0; if (started == 0) { if (d == 0) { ns = 0; np2 = 10; np1 = 10; } else { ns = 1; np2 = 10; np1 = d; } } else { ns = 1; np2 = prev1; np1 = d; if (prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d))) { add = 1; } } auto [tc, tw] = dfs(pos + 1, np2, np1, ns, nlimit); c += tc; w += tw + tc * add; } if (!limit) { vis[pos][prev2][prev1][started] = true; fCnt[pos][prev2][prev1][started] = c; fWav[pos][prev2][prev1][started] = w; } return {c, w}; } }; -
class Solution: def totalWaviness(self, num1: int, num2: int) -> int: def calc(x: int) -> int: if x < 0: return 0 s = str(x) @cache def dfs( pos: int, prev2: int, prev1: int, started: int, limit: bool ) -> tuple: if pos == len(s): return (started, 0) up = int(s[pos]) if limit else 9 cnt = wav = 0 for d in range(up + 1): nlimit = limit and d == up add = 0 if started == 0: if d == 0: ns, np2, np1 = 0, 10, 10 else: ns, np2, np1 = 1, 10, d else: ns, np2, np1 = 1, prev1, d if prev2 != 10 and ( (prev1 > prev2 and prev1 > d) or (prev1 < prev2 and prev1 < d) ): add = 1 c, w = dfs(pos + 1, np2, np1, ns, nlimit) cnt += c wav += w + c * add return cnt, wav return dfs(0, 10, 10, 0, True)[1] return calc(num2) - calc(num1 - 1) -
import "strconv" func totalWaviness(num1 int64, num2 int64) int64 { return calc(num2) - calc(num1-1) } func calc(x int64) int64 { if x < 0 { return 0 } s := strconv.FormatInt(x, 10) n := len(s) var fCnt, fWav [20][11][11][2]int64 var vis [20][11][11][2]bool var dfs func(pos, prev2, prev1, started int, limit bool) (int64, int64) dfs = func(pos, prev2, prev1, started int, limit bool) (int64, int64) { if pos == n { return int64(started), 0 } if !limit && vis[pos][prev2][prev1][started] { return fCnt[pos][prev2][prev1][started], fWav[pos][prev2][prev1][started] } up := 9 if limit { up = int(s[pos] - '0') } var c, w int64 for d := 0; d <= up; d++ { nlimit := limit && d == up ns, np2, np1, add := started, prev1, d, 0 if started == 0 { if d == 0 { ns, np2, np1 = 0, 10, 10 } else { ns, np2, np1 = 1, 10, d } } else if prev2 != 10 && ((prev1 > prev2 && prev1 > d) || (prev1 < prev2 && prev1 < d)) { add = 1 } tc, tw := dfs(pos+1, np2, np1, ns, nlimit) c += tc w += tw + tc*int64(add) } if !limit { vis[pos][prev2][prev1][started] = true fCnt[pos][prev2][prev1][started] = c fWav[pos][prev2][prev1][started] = w } return c, w } _, wav := dfs(0, 10, 10, 0, true) return wav }