0517MediumMathDynamic ProgrammingEnumeration

Serial Number Kinks

Tracked in this browser only

Trains the technique from

LeetCode 3751Total Waviness of Numbers in Range I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def total_kinks(low: int, high: int) -> int:

Java

public int totalKinks(int low, int high)

The intended approach

Time O(d * 10 * 40) for a limit of d digits: the table has at most d * 10 * 4 states, each filled with ten branches.Space O(d * 40) for the table.

Write the answer as the total over 1 through `high` minus the total over 1 through `low - 1`, and count each of those by filling digits left to right. Whether a position is a kink is settled as soon as the digit after it is written, so a partly written serial only needs to remember the last digit written and whether the last step rose, fell or stayed level. A small table over remaining length, last digit and last step gives both how many completions exist and how many kinks they hold between them, and the prefixes that still match the limit are walked digit by digit, carrying the kinks already fixed by that prefix.

Pythonentry point: total_kinks

def total_kinks(low, high):
    # Count kinks for every serial from 1 up to a limit, then subtract the count for
    # everything below low. Reading a serial left to right, a kink at a position is
    # settled the moment the next digit is placed, so a suffix only needs to know
    # the digit just written and whether the last step went up, down or stayed
    # level. That suffix table is shared by every prefix, and the prefixes that stay
    # equal to the limit are walked digit by digit.
    # O(d * 10 * 40) time for a d-digit limit, O(d * 40) space for the table.
    NONE, UP, DOWN, FLAT = 0, 1, 2, 3

    def step(digit, prev):
        if digit > prev:
            return UP
        if digit < prev:
            return DOWN
        return FLAT

    def turns(x):
        d = [int(c) for c in str(x)]
        found = 0
        for p in range(1, len(d) - 1):
            if (d[p] > d[p - 1] and d[p] > d[p + 1]) or (d[p] < d[p - 1] and d[p] < d[p + 1]):
                found += 1
        return found

    table = {}

    def free(slots, prev, way):
        # (how many fillings, total kinks over those fillings) for `slots` more digits
        key = (slots, prev, way)
        if key in table:
            return table[key]
        if slots == 0:
            table[key] = (1, 0)
            return table[key]
        count = 0
        gained = 0
        for digit in range(10):
            nxt = step(digit, prev)
            kink = 1 if (way == UP and nxt == DOWN) or (way == DOWN and nxt == UP) else 0
            c, g = free(slots - 1, digit, nxt)
            count += c
            gained += g + kink * c
        table[key] = (count, gained)
        return table[key]

    def upto(limit):
        if limit <= 0:
            return 0
        d = [int(c) for c in str(limit)]
        n = len(d)
        total = 0
        for length in range(1, n):
            for lead in range(1, 10):
                total += free(length - 1, lead, NONE)[1]
        fixed = 0
        for i in range(n):
            start = 1 if i == 0 else 0
            for digit in range(start, d[i]):
                if i == 0:
                    total += free(n - 1, digit, NONE)[1]
                else:
                    way = step(d[i - 1], d[i - 2]) if i >= 2 else NONE
                    nxt = step(digit, d[i - 1])
                    kink = 1 if (way == UP and nxt == DOWN) or (way == DOWN and nxt == UP) else 0
                    c, g = free(n - 1 - i, digit, nxt)
                    total += g + (fixed + kink) * c
            if i >= 2:
                way = step(d[i - 1], d[i - 2])
                nxt = step(d[i], d[i - 1])
                if (way == UP and nxt == DOWN) or (way == DOWN and nxt == UP):
                    fixed += 1
        return total + turns(limit)

    return upto(high) - upto(low - 1)

The obvious version

Spell out every number in the range and check each interior position against its two neighbours directly, adding up all the kinks found. O((high - low) * d).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_total_kinks(low, high):
    running = 0
    for value in range(low, high + 1):
        text = str(value)
        for p in range(1, len(text) - 1):
            left, here, right = text[p - 1], text[p], text[p + 1]
            if (here > left and here > right) or (here < left and here < right):
                running += 1
    return running

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in