3751. Total Waviness of Numbers in Range I

Intuition

Total waviness over a range is additive, so we can evaluate each number independently and sum the counts. For one number, waviness is determined by local comparisons between each middle digit and its two neighbors. Counting local peaks and valleys directly matches the definition.

Algorithm

1Initialize answer = 0.
2For each x from num1 to num2, compute F(x) and add it to answer.
3In F(x), extract digits into an array from least significant to most significant.
4If digit count is less than 3, waviness is 0.
5For every index i from 1 to m-2, increment count if digit[i] is a strict local maximum or strict local minimum.
6Return the accumulated range sum.

Example Walkthrough

Input: num1 = 120, num2 = 123

1.120 -> digits [0,2,1], middle digit 2 is greater than both neighbors -> waviness 1.
2.121 -> digits [1,2,1], middle digit 2 is greater than both neighbors -> waviness 1.
3.122 -> digits [2,2,1], middle digit 2 is not strictly greater or smaller -> waviness 0.
4.123 -> digits [3,2,1], middle digit 2 is not local extremum -> waviness 0.

Output: 2

Common Pitfalls

•Comparisons must be strict; equal neighboring digits do not form waviness.
•Numbers with fewer than three digits always contribute 0.
•Digit extraction order does not matter for local-extremum counting as long as adjacency is preserved consistently.

3751.cs

// Approach: Brute-force all values in [num1, num2] and compute each number's waviness independently.
// For each number, inspect every middle digit and count local extrema (strictly greater than both neighbors or strictly smaller than both).
// Time: O((num2 - num1 + 1) * d) Space: O(d), where d is number of digits

public 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;
    }
}

Was this solution helpful?