3751-TotalWavinessOfNumbersInRangeI.go

package main

// 3751. Total Waviness of Numbers in Range I
// 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:
//     1. A digit is a peak if it is strictly greater than both of its immediate neighbors.
//     2. A digit is a valley if it is strictly less than both of its immediate neighbors.
//     3. The first and last digits of a number cannot be peaks or valleys.
//     4. 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 <= 10^5

import "fmt"

// time: O(n log m), space: O(log m)
func totalWaviness(num1 int, num2 int) int {
    res := 0
    countWaviness := func(v int) int { // time: O(log num), space: O(log num)
        s := fmt.Sprint(v)
        res := 0
        for i, l := 1, len(s)-1; i < l; i++ {
            if (s[i-1] < s[i] && s[i+1] < s[i]) || (s[i-1] > s[i] && s[i+1] > s[i]) {
                res++
            }
        }
        return res
    }
    for i := num1; i <= num2; i++ {
        res += countWaviness(i)
    }
    return res
}

func totalWaviness1(num1 int, num2 int) int {
    res := 0
    countWaviness := func(v int) int {
        nums := make([]int, 0, 20)
        for v > 0 {
            nums = append(nums, v%10)
            v /= 10
        }
        n := len(nums)
        if n < 3 {
            return 0
        }
        res := 0
        for i := 1; i < n-1; i++ {
            if (nums[i] > nums[i-1] && nums[i] > nums[i+1]) || (nums[i] < nums[i-1] && nums[i] < nums[i+1]) {
                res++
            }
        }
        return res  
    }
    for i := num1; i <= num2; i++ {
        res += countWaviness(i)
    }
    return res
}

func main() {
    // 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.
    fmt.Println(totalWaviness(120, 130)) // 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.
    fmt.Println(totalWaviness(120, 130)) // 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.
    fmt.Println(totalWaviness(4848, 4848)) // 2

    fmt.Println(totalWaviness(1, 1)) // 0
    fmt.Println(totalWaviness(1, 1024)) // 543
    fmt.Println(totalWaviness(1, 1_000_000)) // 2230005
    fmt.Println(totalWaviness(1024, 1024)) // 1
    fmt.Println(totalWaviness(1024, 1_000_000)) // 2229463
    fmt.Println(totalWaviness(1_000_000, 1_000_000)) // 0

    fmt.Println(totalWaviness1(120, 130)) // 3   
    fmt.Println(totalWaviness1(120, 130)) // 3   
    fmt.Println(totalWaviness1(4848, 4848)) // 2
    fmt.Println(totalWaviness1(1, 1)) // 0
    fmt.Println(totalWaviness1(1, 1024)) // 543
    fmt.Println(totalWaviness1(1, 1_000_000)) // 2230005
    fmt.Println(totalWaviness1(1024, 1024)) // 1
    fmt.Println(totalWaviness1(1024, 1_000_000)) // 2229463
    fmt.Println(totalWaviness1(1_000_000, 1_000_000)) // 0
}