A seismograph assigns every tremor it detects a positive integer reading id, printed as a decimal number with no leading zeros. Reading the digits of an id from left to right as a trace, call a digit position a kink if it is neither the first nor the last digit of the id, and its digit is strictly greater than both of its two immediate neighboring digits, or strictly less than both of them. (An id with fewer than 3 digits has no interior position at all, so its kink count is always 0.)
Given the ids L and R of the first and last tremor in a logging window (L <= R), compute the sum of the kink counts of every integer id from L to R, inclusive.
A single line containing two integers L and R, separated by a space.
A single integer: the sum of kink counts over every id in [L, R].
1 <= L <= R <= 200000Example 1
Input
1 20
Expected
0
Explanation
Every id from 1 to 20 has at most 2 digits, and a kink can only occur at an interior digit position, which requires at least 3 digits. So every id in this range has kink count 0, and the total is 0.
Example 2
Input
100 105
Expected
5
Explanation
Id 100 has digits 1,0,0: the middle digit 0 is not strictly less than both neighbors (it ties the second neighbor, also 0), so it has kink count 0. Ids 101 through 105 all have the shape 1,0,d with d from 1 to 5: the middle digit 0 is strictly less than both neighbors (1 and d), so each has kink count 1. Summing 0+1+1+1+1+1 over ids 100..105 gives 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →