Total Waviness of Numbers in Range I

medium math enumeration digits

Problem

Given an inclusive range [num1, num2], the waviness of a number is the count of its interior digits that are peaks or valleys. A digit is a peak if it is strictly greater than both neighbors, a valley if strictly less than both. The first and last digits never count, so numbers with fewer than 3 digits have waviness 0. Return the total waviness summed over every number in the range.

Inputnum1 = 120, num2 = 130

Output3

120, 121 and 130 each have one peak (the middle 2 or 3); all others are flat. 1 + 1 + 1 = 3.

num1

num2

def totalWaviness(num1, num2):
    total = 0
    for n in range(num1, num2 + 1):
        d = [int(ch) for ch in str(n)]   # digits of n
        for i in range(1, len(d) - 1):   # interior digits only
            peak = d[i] > d[i - 1] and d[i] > d[i + 1]
            valley = d[i] < d[i - 1] and d[i] < d[i + 1]
            if peak or valley:
                total += 1
    return total

function totalWaviness(num1, num2) {
  let total = 0;
  for (let n = num1; n <= num2; n++) {
    const d = String(n).split("").map(Number); // digits of n
    for (let i = 1; i < d.length - 1; i++) {    // interior digits
      const peak = d[i] > d[i - 1] && d[i] > d[i + 1];
      const valley = d[i] < d[i - 1] && d[i] < d[i + 1];
      if (peak || valley) total++;
    }
  }
  return total;
}

int totalWaviness(int num1, int num2) {
    int total = 0;
    for (int n = num1; n <= num2; n++) {
        char[] d = Integer.toString(n).toCharArray(); // digits
        for (int i = 1; i < d.length - 1; i++) {      // interior
            boolean peak = d[i] > d[i - 1] && d[i] > d[i + 1];
            boolean valley = d[i] < d[i - 1] && d[i] < d[i + 1];
            if (peak || valley) total++;
        }
    }
    return total;
}

int totalWaviness(int num1, int num2) {
    int total = 0;
    for (int n = num1; n <= num2; n++) {
        string d = to_string(n);              // digits of n
        for (int i = 1; i + 1 < (int)d.size(); i++) { // interior
            bool peak = d[i] > d[i - 1] && d[i] > d[i + 1];
            bool valley = d[i] < d[i - 1] && d[i] < d[i + 1];
            if (peak || valley) total++;
        }
    }
    return total;
}

Explanation

Because the range is small (num2 ≤ 10⁵), we can simply enumerate every number in [num1, num2] and measure each one's waviness directly.

To measure one number we look at its decimal digits as a sequence. Only the interior digits (everything except the first and last) can be a peak or a valley, so we scan indices 1 .. len-2.

For each interior digit d[i] we compare it against its left neighbor d[i-1] and right neighbor d[i+1]. It is a peak when it is strictly greater than both, and a valley when it is strictly less than both. Equal neighbors break the strictness, so plateaus count for nothing.

Each peak or valley contributes 1 to a running total. Numbers with fewer than three digits have no interior positions, so the inner loop simply never runs and they add nothing.

For the range [120, 130]: 120, 121 and 130 each have one peaked middle digit, every other number is monotone or two-digit-flat, so the total comes to 3.

Time: O((num2 − num1) · D) Space: O(D)