Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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:
[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.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.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 <= 105Problem summary: 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].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Dynamic Programming
120 130
198 202
4848 4848
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3751: Total Waviness of Numbers in Range I
class Solution {
public int totalWaviness(int num1, int num2) {
int ans = 0;
for (int x = num1; x <= num2; x++) {
ans += f(x);
}
return ans;
}
private int f(int x) {
int[] nums = new int[20];
int m = 0;
while (x > 0) {
nums[m++] = x % 10;
x /= 10;
}
if (m < 3) {
return 0;
}
int s = 0;
for (int i = 1; i < m - 1; i++) {
if ((nums[i] > nums[i - 1] && nums[i] > nums[i + 1])
|| (nums[i] < nums[i - 1] && nums[i] < nums[i + 1])) {
s++;
}
}
return s;
}
}
// Accepted solution for LeetCode #3751: Total Waviness of Numbers in Range I
func totalWaviness(num1 int, num2 int) (ans int) {
for x := num1; x <= num2; x++ {
ans += f(x)
}
return
}
func f(x int) int {
nums := make([]int, 0, 20)
for x > 0 {
nums = append(nums, x%10)
x /= 10
}
m := len(nums)
if m < 3 {
return 0
}
s := 0
for i := 1; i < m-1; i++ {
if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) ||
(nums[i] < nums[i-1] && nums[i] < nums[i+1]) {
s++
}
}
return s
}
# Accepted solution for LeetCode #3751: Total Waviness of Numbers in Range I
class Solution:
def totalWaviness(self, num1: int, num2: int) -> int:
def f(x: int) -> int:
nums = []
while x:
nums.append(x % 10)
x //= 10
m = len(nums)
if m < 3:
return 0
s = 0
for i in range(1, m - 1):
if nums[i] > nums[i - 1] and nums[i] > nums[i + 1]:
s += 1
elif nums[i] < nums[i - 1] and nums[i] < nums[i + 1]:
s += 1
return s
return sum(f(x) for x in range(num1, num2 + 1))
// Accepted solution for LeetCode #3751: Total Waviness of Numbers in Range I
fn total_waiviness(num1: i32, num2: i32) -> i32 {
fn count_peak_and_valley(n: i32) -> i32 {
let s : Vec<_> = n.to_string().bytes().collect();
let len = s.len();
let mut ret = 0;
for i in 1..(len - 1) {
if (s[i-1] < s[i] && s[i] > s[i + 1]) || (s[i - 1] > s[i] && s[i] < s[i + 1]) {
ret += 1;
}
}
ret
}
(num1..=num2)
.fold(0, |acc, n| acc + count_peak_and_valley(n))
}
fn main() {
let ret = total_waiviness(1, 10000);
println!("ret={ret}");
}
#[test]
fn test() {
assert_eq!(total_waiviness(120, 130), 3);
assert_eq!(total_waiviness(198, 202), 3);
assert_eq!(total_waiviness(4848, 4848), 2);
}
// Accepted solution for LeetCode #3751: Total Waviness of Numbers in Range I
function totalWaviness(num1: number, num2: number): number {
let ans = 0;
for (let x = num1; x <= num2; x++) {
ans += f(x);
}
return ans;
}
function f(x: number): number {
const nums: number[] = [];
while (x > 0) {
nums.push(x % 10);
x = Math.floor(x / 10);
}
const m = nums.length;
if (m < 3) return 0;
let s = 0;
for (let i = 1; i < m - 1; i++) {
if (
(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) ||
(nums[i] < nums[i - 1] && nums[i] < nums[i + 1])
) {
s++;
}
}
return s;
}
Use this to step through a reusable interview workflow for this problem.
Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.
Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.