Show problems as
Classic problem #1387MediumDynamic ProgrammingMemoizationSorting

Sort Integers by The Power Value

Real-world version: Kth Slowest Dial Reading To Settle
Tracked in this browser only
Read Sort Integers by The Power Value on LeetCode(opens in a new tab)

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

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

Python
def kth_by_settling(low: int, high: int, k: int) -> int:
Java
public int kthBySettling(int low, int high, int k)

More on the same topics