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.
[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
This code calculates the total "waviness" of all integers within a given range from num1 to num2, where "waviness" (or volatility) is defined as the number of times a sequence of three consecutive digits changes direction to form a peak (going up then down, like 1-3-2) or a valley (going down then up, like 3-1-2). To do this efficiently without manually checking every single number, the code uses a technique called Digit Dynamic Programming inside a helper function (solve) to build numbers digit-by-digit from left to right, counting the peaks and valleys mathematically for multiple numbers at once. Finally, it finds the total waviness for the entire range by calculating the accumulated waviness up to the upper limit (num2) and subtracting the waviness of all numbers up to just before the lower limit (num1 - 1).
var totalWaviness = function (num1, num2) {
// calculate the sum of the volatility values of all numbers in [0, num]
const solve = (num) => {
// if the number has fewer than 3 digits, the fluctuation value is 0
if (num < 100) {
return 0;
}
const s = num.toString();
const n = s.length;
let currStates = [];
// digit 10 represents the invalid state when there is a leading zero
currStates.push({
prev: 10,
curr: 10,
tight: 1,
lead: 1,
cnt: 1,
sum: 0,
});
for (let pos = 0; pos < n; ++pos) {
const limit = parseInt(s[pos]);
// use a four-dimensional array for temporary storage, dimensions: [tight][lead][prev][curr]
const cnt = Array(2)
.fill()
.map(() =>
Array(2)
.fill()
.map(() =>
Array(11)
.fill()
.map(() => Array(11).fill(0)),
),
);
const sumArr = Array(2)
.fill()
.map(() =>
Array(2)
.fill()
.map(() =>
Array(11)
.fill()
.map(() => Array(11).fill(0)),
),
);
for (const st of currStates) {
const maxDigit = st.tight ? limit : 9;
for (let digit = 0; digit <= maxDigit; ++digit) {
const newLead = st.lead && digit === 0 ? 1 : 0;
const newPrev = st.curr;
const newCurr = newLead ? 10 : digit;
const newTight = st.tight && digit === maxDigit ? 1 : 0;
let add = 0;
// calculate fluctuation only when there are three significant digits (both prev and curr are valid and not leading zeros)
if (!newLead && st.prev !== 10 && st.curr !== 10) {
if (
(st.prev < st.curr && st.curr > digit) ||
(st.prev > st.curr && st.curr < digit)
) {
add = st.cnt;
}
}
cnt[newTight][newLead][newPrev][newCurr] += st.cnt;
sumArr[newTight][newLead][newPrev][newCurr] += st.sum + add;
}
}
// collect legal states
const nextStates = [];
for (let tight = 0; tight < 2; ++tight) {
for (let lead = 0; lead < 2; ++lead) {
for (let prev = 0; prev <= 10; ++prev) {
for (let curr = 0; curr <= 10; ++curr) {
const c = cnt[tight][lead][prev][curr];
const sVal = sumArr[tight][lead][prev][curr];
// if the current state is valid, proceed to the next round of calculation
if (c !== 0) {
nextStates.push({
prev,
curr,
tight,
lead,
cnt: c,
sum: sVal,
});
}
}
}
}
}
currStates = nextStates;
}
// sum of fluctuation values of all valid states
let ans = 0;
for (const st of currStates) {
ans += st.sum;
}
return ans;
};
return solve(num2) - solve(num1 - 1);
};