0786MediumDynamic ProgrammingMemoizationSorting

Kth Slowest Dial Reading To Settle

Tracked in this browser only

Trains the technique from

LeetCode 1387Sort Integers by The Power Value

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 calibration rig winds a dial down to its resting mark. The dial shows a positive whole number, and one adjustment changes the reading like this:

an even reading is halved;
an odd reading is tripled and then one is added.

Adjustments are repeated until the reading is 1, which is the resting mark. The settling count of a reading is how many adjustments that takes, so the settling count of 1 is 0 and the settling count of 16 is 4 because 16 steps down through 8, 4, 2 to 1. Every reading allowed here does reach 1 eventually, so the settling count is always a finite number.

The rig is tested at every whole reading from low to high inclusive. List those readings in increasing order of settling count; where two readings have the same settling count, put the smaller reading first. That ordering is total, so no ambiguity remains.

Return the k-th reading in that list, counting from 1.

Examples

Example 1

Input: low = 10, high = 13, k = 3
Output: 13

The settling counts are 6 for reading 10, 14 for 11, 9 for 12 and 9 for 13. Ordered by count that gives 10, then 12 and 13 which are tied on 9 and so go smaller first, then 11. The third entry of that list is 13.

Example 2

Input: low = 4, high = 9, k = 2
Output: 8

Reading 4 settles in 2 adjustments and reading 8 in 3, while 5 takes 5, 6 takes 8, 7 takes 16 and 9 takes 19. The list therefore opens 4, 8, 5, 6, 7, 9 and its second entry is 8.

Example 3

Input: low = 6, high = 6, k = 1
Output: 6

Only one reading is tested, so it is the first entry of the list.

Constraints

1 <= low <= high <= 1000
1 <= k <= high - low + 1

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 kth_by_settling(low: int, high: int, k: int) -> int:

Java

public int kthBySettling(int low, int high, int k)

The intended approach

Time O(m log m + W) where m = high - low + 1 and W is the number of adjustment steps walked, each distinct reading being walked at most once.Space O(m + d): the sorted list of m readings plus d cached readings, d counting the readings above high that the walks pass through.

Settling counts are computed with a cache keyed by reading. To count a reading, walk the adjustments forward, pushing each unknown reading onto a stack, until a reading with a known count appears; then unwind the stack, each popped reading being one adjustment further from the resting mark than the one after it. Readings from other starts, and readings above `high` visited along the way, all land in the same cache. Finally sort the range on the pair (settling count, reading) and index the k-th entry, the second component supplying the smaller-reading-first tie-break.

Pythonentry point: kth_by_settling

def kth_by_settling(low, high, k):
    # Chains overlap heavily, so every reading whose count is already known is
    # reused: walk forward onto a stack until a known reading turns up, then
    # unwind the stack filling in counts one step apart. Ordering is a plain sort
    # on the pair (count, reading), which puts the smaller reading first on a tie.
    # Time O(m log m + total walked steps) for m = high - low + 1, the walked steps
    # being paid once per distinct reading thanks to the cache.
    # Space O(m + d) for the sorted readings and the d cached readings.
    known = {1: 0}

    def settling(start):
        pending = []
        cur = start
        while cur not in known:
            pending.append(cur)
            cur = cur // 2 if cur % 2 == 0 else 3 * cur + 1
        steps = known[cur]
        while pending:
            steps += 1
            known[pending.pop()] = steps
        return steps

    ordered = sorted(range(low, high + 1), key=lambda v: (settling(v), v))
    return ordered[k - 1]

The obvious version

Count adjustments separately for every reading with no sharing, then find the answer without sorting: for each reading, count how many readings of the range come before it under the (count, reading) rule, and return the one with exactly k-1 ahead of it.

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_kth_by_settling(low, high, k):
    counts = {}
    for v in range(low, high + 1):
        cur = v
        steps = 0
        while cur != 1:
            cur = cur // 2 if cur % 2 == 0 else 3 * cur + 1
            steps += 1
        counts[v] = steps
    for v in range(low, high + 1):
        ahead = 0
        for u in range(low, high + 1):
            if (counts[u], u) < (counts[v], v):
                ahead += 1
        if ahead + 1 == k:
            return v
    return -1

How this problem was checked

Reference solution executed against 14 test cases — 14 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