Rank by Hailstone Steps
MediumSorting & Searching
Problem
The hailstone process transforms a positive integer x: if x is even it becomes x / 2, otherwise 3x + 1. The *steps* of x are how many transformations it takes to reach 1 (so 1 has 0 steps, 2 has 1, and 3 has 7: 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1).
Take every integer from low to high inclusive and sort them by steps ascending, breaking ties by the smaller number. Return the number at 1-based position rank in that order.
Example 1
- Input:
- low = 5, high = 10, rank = 2
- Output:
- 5
Steps: 5 → 5, 6 → 8, 7 → 16, 8 → 3, 9 → 19, 10 → 6. Sorted: 8, 5, 10, 6, 7, 9; the second is 5.
Example 2
- Input:
- low = 1, high = 1, rank = 1
- Output:
- 1
Constraints
- 1 ≤ low ≤ high ≤ 1000
- 1 ≤ rank ≤ high - low + 1
Hint
Show the first hint
This is a sort with a computed key. What is the key?
Walkthrough
How to approach it
01Clarify before coding
- Is 1 counted as 0 steps? Yes.
- Is rank 1-based? Yes, rank 1 is the first element after sorting.
- Do intermediate values stay within safe integers? Yes: from numbers ≤ 1000 the trajectories peak around 250 000.
02Brute force
Simulate each number's trajectory from scratch, sort by (steps, value), index rank - 1.
Cost: O(m · L + m log m) for m numbers with trajectories of length L (≤ 179 here): acceptable, but repeated work.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.