Show problems as
Classic problem #3751MediumMathDynamic ProgrammingEnumeration

Total Waviness of Numbers in Range I

Real-world version: Serial Number Kinks
Tracked in this browser only
Read Total Waviness of Numbers in Range I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A serial number is written in decimal with no leading zeros. A digit position of a serial number is a kink when that position has a digit on each side of it and its digit is either strictly larger than both neighbouring digits or strictly smaller than both. The leading digit and the trailing digit have only one neighbour, so neither is ever a kink, and a serial number of one or two digits has no kinks at all.

The kink count of a serial number is how many of its positions are kinks. For example 2718 has one kink, at the digit 1, because 1 is smaller than the 7 before it and smaller than the 8 after it.

Return the total kink count of every whole number from low to high, both included.

Examples

Example 1

Input
low = 100, high = 120
Output
10

Between 100 and 120 the serials 102 through 109 each have a kink at the middle digit, since 0 is smaller than the 1 before it and smaller than the digit after it, and 120 has one at the 2, giving 9 kinks in total.

Example 2

Input
low = 1221, high = 1221
Output
0

The two middle digits of 1221 are each equal to a neighbour, so neither is strictly larger or strictly smaller than both of its neighbours and the kink count is 0.

Example 3

Input
low = 1212, high = 1212
Output
2

In 1212 the 2 at the second position is larger than both neighbours and the 1 at the third position is smaller than both, so the kink count is 2.

Constraints

  • 1 <= low <= high <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def total_kinks(low: int, high: int) -> int:
Java
public int totalKinks(int low, int high)

More on the same topics