4128 Total Waviness Of Numbers In Range Ii
4128 Total Waviness Of Numbers In Range Ii
Total Waviness of Numbers in Range II 
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:
1
2
3
4
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]:
1
2
3
4
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]:
1
2
3
4
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
1 <= num1 <= num2 <= 1015
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution:
def solve(self, num: int) -> int:
# if the number has fewer than 3 digits, the fluctuation value is 0
if num < 100:
return 0
s = str(num)
n = len(s)
# digit 10 represents the invalid state when there is a leading zero
curr_states = [
(10, 10, 1, 1, 1, 0)
] # (prev, curr, tight, lead, cnt, sum)
for pos in range(n):
limit = int(s[pos])
cnt = [
[[[0] * 11 for _ in range(11)] for _ in range(2)]
for _ in range(2)
]
sum_arr = [
[[[0] * 11 for _ in range(11)] for _ in range(2)]
for _ in range(2)
]
for prev, curr, tight, lead, c, s_val in curr_states:
max_digit = limit if tight else 9
for digit in range(max_digit + 1):
new_lead = 1 if (lead and digit == 0) else 0
new_prev = curr
new_curr = 10 if new_lead else digit
new_tight = 1 if (tight and digit == max_digit) else 0
add = 0
# calculate fluctuation only when there are three significant digits (both prev and curr are valid and not leading zeros)
if not new_lead and prev != 10 and curr != 10:
if (prev < curr and curr > digit) or (
prev > curr and curr < digit
):
add = c
cnt[new_tight][new_lead][new_prev][new_curr] += c
sum_arr[new_tight][new_lead][new_prev][new_curr] += (
s_val + add
)
# collect legal states
next_states = []
for tight in range(2):
for lead in range(2):
for prev in range(11):
for cur in range(11):
c = cnt[tight][lead][prev][cur]
if c != 0:
next_states.append(
(
prev,
cur,
tight,
lead,
c,
sum_arr[tight][lead][prev][cur],
)
)
curr_states = next_states
# sum of fluctuation values of all valid states
ans = 0
for _, _, _, _, _, s_val in curr_states:
ans += s_val
return ans
def totalWaviness(self, num1: int, num2: int) -> int:
return self.solve(num2) - self.solve(num1 - 1)
This post is licensed under CC BY 4.0 by the author.