Total Digit Waviness Across a Large Range

### Problem Given integers `num1` and `num2`, return the total waviness of all integers in the inclusive range `[num1,num2]`. Use the ordinary decimal representation of each number, without leading zeros. Its waviness counts the interior digits that are either: - Peaks, strictly greater than both immediate neighbors. - Valleys, strictly less than both immediate neighbors. The first and last digits never contribute. Numbers with fewer than three digits have waviness zero. Equality with a neighbor is insufficient for a strict peak or valley. ```cpp class Solution { public: long long totalWaviness(long long num1, long long num2); }; ``` ### Examples **Example 1:** ```text Input: num1 = 909, num2 = 912 Output: 2 Explanation: The middle zero in 909 and the middle one in 912 are valleys, one contribution each. The middle digits of 910 and 911 are neither strict peaks nor strict valleys. ``` **Example 2:** ```text Input: num1 = 1210, num2 = 1212 Output: 4 Explanation: The waviness values for 1210, 1211, and 1212 are 1,1,2. Each has a peak at its second digit; only 1212 also has a valley at its third digit. ``` ### Constraints - `1 <= num1 <= num2 <= 1000000000000000`. ### Clarifying Questions - Are both range endpoints counted? Yes. - Can a number contribute more than once? Yes; each qualifying interior position contributes one. - Do equal adjacent digits ever satisfy a strict comparison? No. - Are digits from different numbers compared? No; each number is evaluated independently. - Must the wide input and return types be retained? Yes; preserve both `long long` parameters and the `long long` result. ### What a Strong Answer Covers - The complete strict peak/valley definition and the excluded endpoint digits. - The inclusive range, short numbers, internal zeros, and equal digits. - A proof that each contributing position is counted exactly once. - Numeric safety and resource bounds covering the largest endpoint. ### Follow-up Questions - How would requesting the waviness of every individual number change output size? - What would need to be specified before using another numeric base? ```hint Aggregate the contribution when its right neighbor arrives Count a prefix range up to a bound using digit dynamic programming, keeping the last two significant digits and whether the bound is still tight. Ignore leading padding zeros, but retain internal zeros. Store both the number of prefixes and the sum of their accumulated waviness so each newly completed peak or valley is added for all represented prefixes. Subtract two inclusive prefix totals for the requested range. ```