3753. Total Waviness of Numbers in Range II

Difficulty: Hard

Topics: Senior Staff, Math, Dynamic Programming, Biweekly Contest 170

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.

Example 4:

Input: num1 = 63, num2 = 101
Output: 1

Constraints:

1 <= num1 <= num2 <= 10¹⁵

Hint:

Use digit dynamic programming
Build a digit-DP state (position, tight, lastDigit, secondLastDigit)

Solution:

This solution calculates the total sum of waviness for all numbers in a given inclusive range [num1, num2].

Waviness is defined as the count of peaks and valleys in the digit sequence of a number (excluding first and last digits).

The approach uses digit dynamic programming (digit DP) to efficiently process ranges up to 10^15, avoiding brute-force enumeration.

The function totalWaviness(num1, num2) computes the result as solve(num2) - solve(num1 - 1), where solve(n) returns the total waviness for [1, n].

Approach:

Digit DP – We recursively process digits from most significant to least significant.
State – (position, tight, started, secondLast, last) tracks:
- current index in the number
- whether we are bound by the prefix of n (tight)
- whether we have started placing non-leading digits (started)
- the previous two digits (secondLast, last) to detect peaks/valleys
Memoization – For !tight states, we store results to reuse across different numbers.
Contribution counting – When we place a new digit:
- If we have at least 3 digits so far (secondLast !== -1), we check if the middle digit (last) is a peak or valley.
- If yes, we add 1 × (number of valid suffixes) to the waviness sum.
Base case – When all digits are placed (pos == len), return count = 1, waviness = 0.
Range subtraction – totalWaviness(num1, num2) = solve(num2) - solve(num1 - 1).

Let's implement this solution in PHP: 3753. Total Waviness of Numbers in Range II

<?php
/**
 * @param Integer $num1
 * @param Integer $num2
 * @return Integer
 */
function totalWaviness(int $num1, int $num2): int
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * @param int $n
 * @return int|mixed
 */
function sumWavinessUpTo(int $n): mixed
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo totalWaviness(120, 130) . "\n";            // Output: 3
echo totalWaviness(198, 202) . "\n";            // Output: 3
echo totalWaviness(4848, 4848) . "\n";          // Output: 2
echo totalWaviness(63, 101) . "\n";             // Output: 1
?>

Explanation:

Peak & Valley definition
- A digit d is a peak if prev < d > next.
- A digit d is a valley if prev > d < next.
- First and last digits are ignored.
Digit DP state We need the last two digits to know if the current position (as the second last) is a peak/valley when the next digit is chosen.
Transition
- At position pos, we try digits 0..limit:
  - If not started and digit is 0, stay in not started.
  - If not started and digit > 0, start the number, store it as last, secondLast = -1.
  - If started, compute if last (which is the middle digit between secondLast and digit) is peak/valley, and add to waviness accordingly.
Memoization The result for a state (pos, started, secondLast, last) with tight = 0 can be reused across different higher prefixes.
Complexity State count is O(len × 2 × 10 × 10) with len ≤ 16 → very fast.

Complexity

Time Complexity: O(len × 2 × 10 × 10 × 10) ≈ O(16 × 1000) = O(16000) per solve(n), which is trivial for input sizes up to 10¹⁵.
Space Complexity: O(len × 2 × 10 × 10) for memoization table.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

LinkedIn
GitHub