3753. Total Waviness of Numbers in Range II

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.

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.

 

Constraints:

• 1 <= num1 <= num2 <= 1015​​​​​​​

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(log(num2)*1010)
• Space complexity: O(log(num2)*100)

 

JavaScript

/**
 * @param {number} num1
 * @param {number} num2
 * @return {number}
 */
const totalWaviness = function (num1, num2) {
  const getWaviness = num => {
    if (num < 100) return 0;

    const target = `${num}`;
    const n = target.length;

    const dp = Array.from({ length: n }, () => {
      return new Array(100).fill(-1);
    });

    const getNextWaviness = (index, prev1, prev2, started, tight) => {
      if (index >= n) return { count: 1, waviness: 0 };

      const isValidPrev = started && prev1 !== -1 && prev2 !== -1;
      const prevKey = 10 * prev1 + prev2;

      if (isValidPrev && !tight && dp[index][prevKey] !== -1) {
        return dp[index][prevKey];
      }

      const limit = tight ? Number(target[index]) : 9;
      const result = { count: 0, waviness: 0 };

      for (let current = 0; current <= limit; current++) {
        const nextTight = tight && current === limit;

        if (!started && !current) {
          const next = getNextWaviness(index + 1, -1, -1, false, nextTight);

          result.count += next.count;
          result.waviness += next.waviness;
        } else {
          const isPeaks = current < prev2 && prev1 < prev2;
          const isValleys = current > prev2 && prev1 > prev2;
          const isWaviness = isValidPrev && (isPeaks || isValleys);
          const next = getNextWaviness(index + 1, prev2, current, true, nextTight);

          result.count += next.count;
          result.waviness += next.waviness + (isWaviness ? next.count : 0);
        }
      }

      if (isValidPrev && !tight) {
        dp[index][prevKey] = result;
      }

      return result;
    };

    return getNextWaviness(0, -1, -1, false, true).waviness;
  };

  return getWaviness(num2) - getWaviness(num1 - 1);
};