Count Wavy Numbers
A positive integer is wavy when no two neighboring digits are equal and every digit other than the first and the last is either larger than both of its neighbors or smaller than both. Every one-digit number is wavy. For example, 7, 42, 352 and 3142 are wavy, while 11, 123 and 3443 are not.
Return how many wavy numbers lie between 1 and n, both included.
Example 1
n 100
returns 90
All 9 one-digit numbers, plus the 81 two-digit numbers whose two digits differ. 100 repeats its 0.
Example 2
n 130
returns 102
Past the 90 numbers up to 99, the wavy ones are 101 to 109, 120, 121 and 130: 12 more.
Constraints
1 <= n <= 10**15
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.