Total Digit Waviness Across a Range
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Given integers `num1` and `num2`, return the sum of the waviness of every integer in the inclusive range `[num1,num2]`.
Use each number's ordinary decimal representation without leading zeros. An interior digit contributes one to waviness when it is either:
- A peak: strictly greater than both immediate neighbors.
- A valley: strictly less than both immediate neighbors.
The first and last digits cannot contribute. Numbers with fewer than three digits have waviness zero. Equal neighboring digits do not satisfy a strict comparison.
```cpp
class Solution {
public:
int totalWaviness(int num1, int num2);
};
```
### Examples
**Example 1:**
```text
Input: num1 = 98, num2 = 102
Output: 2
Explanation: 98 and 99 have fewer than three digits. The middle zero in 100 equals its right neighbor, so it contributes nothing. In both 101 and 102, the middle zero is a valley, giving 0+0+0+1+1 = 2.
```
**Example 2:**
```text
Input: num1 = 7070, num2 = 7070
Output: 2
Explanation: In 7070, the second digit 0 is a valley and the third digit 7 is a peak. The endpoint digits do not contribute.
```
### Constraints
- `1 <= num1 <= num2 <= 100000`.
### Clarifying Questions
- Are both range endpoints included? Yes, including a range containing one number.
- Can a number have multiple contributing digits? Yes.
- Does an interior zero count automatically? No; it must satisfy both strict comparisons.
- Are digits across two different numbers compared? No; each number's waviness is determined independently.
### What a Strong Answer Covers
- Ordinary decimal digits, both strict extremum definitions, and excluded endpoints.
- The inclusive range and correct treatment of short numbers and equal digits.
- Counting every eligible interior digit once.
- A completeness proof, numeric bound, and resource analysis for the full range.
### Follow-up Questions
- How would requesting a separate waviness value for each number change the output size?
- What would need clarification if representations in another base were allowed?
```hint Use this version's bounded range
Visit each number in the inclusive range, obtain its decimal digits, and check every position with both a left and right neighbor. Apply the peak and valley inequalities directly, then add the contributions.
```
Overview: Sum strict digit peaks and valleys over an inclusive range up to 100000. Includes fresh examples, equal-digit cases, proof, and a C++ solution.
