Skip to main content
Talentd

Sort Integers by The Power Value - Solution & Explanation

MediumDynamic ProgrammingMemoizationSorting15 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

  • if x is even then x = x / 2
  • if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the kth integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in a 32-bit signed integer.

 

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

 

Constraints:

  • 1 <= lo <= hi <= 1000
  • 1 <= k <= hi - lo + 1

Approach Overview

Problem Overview: Given integers lo, hi, and k, compute the power value for every number in the range. The power value is the number of steps required to reduce a number to 1 using the Collatz rules: if even divide by 2, if odd multiply by 3 and add 1. After computing power values, sort the integers by power (and by value if tied) and return the k-th element.

Approach 1: Direct Power Calculation and Sorting (Time: O(n log n * k), Space: O(n))

Iterate through every integer from lo to hi and compute its power value by repeatedly applying the Collatz transformation until reaching 1. Store pairs like (power, value) in a list. Once all values are processed, sort the list by power first and by integer value as a tiebreaker using standard sorting. Finally return the value at index k - 1. This approach is straightforward and works well for the given constraints, but many power calculations repeat the same intermediate numbers.

Approach 2: Memoization for Power Calculation (Time: O(n log n), Space: O(n))

The Collatz sequence frequently revisits numbers whose power values were already computed. Use memoization to cache results in a hash map where memo[x] stores the power of x. When computing the power for a new number, check the cache before continuing the sequence. If an intermediate value already exists in the map, reuse it and stop the traversal early. This reduces repeated work significantly. After computing powers for all numbers, sort the (power, value) pairs using the same rule as before. The memo table effectively turns repeated sequence work into constant-time lookups and behaves like a lightweight dynamic programming cache.

Recommended for interviews: The memoization approach is what most interviewers expect. The direct calculation demonstrates understanding of the Collatz process and sorting mechanics, but caching intermediate results shows awareness of repeated subproblems and optimization using dynamic programming techniques.

Approach 1: Direct Power Calculation and Sorting

This approach involves calculating the power value of each integer in the range [lo, hi] by simulating the steps to transform the number into 1. Once the power values are calculated, the list of integers is sorted by their power value (breaking ties using their magnitude). Finally, the k-th integer is retrieved.

The function calculate_power(x) computes the power value of x by iterating until x becomes 1. For each integer in the range [lo, hi], the power value is calculated and stored in a list. This list is then sorted by power value and magnitude. The k-th integer is returned from this sorted list.

Code

PythonJavaScriptC#

Python

JavaScript

C#

Complexity

Time Complexity: O(n * m), where n is the number of integers between lo and hi, and m is the average number of steps to reduce an integer to 1.
Space Complexity: O(n) for storing the power values.

Try this approach in the editor →

Approach 2: Memoization for Power Calculation

This approach improves on the first by using memoization to store previously calculated power values, which reduces redundant calculations and enhances performance when calculating power for subsequent numbers.

The calculatePower method utilizes memoization by storing calculated power values in a hashmap to avoid recalculating them. The result is a more efficient computation for subsequent numbers. Power values for the range [lo, hi] are computed, stored, and sorted as before, allowing retrieval of the k-th element.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n log n) for sorting, as calculations are faster with memoization.
Space Complexity: O(n) for the power cache and list storage.

Try this approach in the editor →

Approach 3: Custom Sorting

First, we define a function f(x), which represents the number of steps required to transform the number x into 1, i.e., the power value of the number x.

Then, we sort all the numbers in the interval [lo, hi] in ascending order based on their power values. If the power values are the same, we sort them in ascending order based on the numbers themselves.

Finally, we return the k-th number in the sorted list.

The time complexity is O(n times log n times M), and the space complexity is O(n). Here, n is the number of numbers in the interval [lo, hi], and M is the maximum value of f(x), which is at most 178 in this problem.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Direct Power Calculation and Sorting

Time Complexity: O(n * m), where n is the number of integers between lo and hi, and m is the average number of steps to reduce an integer to 1.
Space Complexity: O(n) for storing the power values.

Memoization for Power Calculation

Time Complexity: O(n log n) for sorting, as calculations are faster with memoization.
Space Complexity: O(n) for the power cache and list storage.

Custom Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Power Calculation and SortingO(n log n * k)O(n)Good baseline solution when implementing Collatz steps directly without optimization.
Memoization for Power CalculationO(n log n)O(n)Best choice when many sequences share intermediate values; avoids recomputation.

Video Solution

17. Sort Integers by The Power Value | Dynamic Programming Series | LeetCode Medium 1387 • AceCoder Academy • 2,984 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sort Integers by The Power Value easy or hard?
Sort Integers by The Power Value is rated Medium difficulty. The main challenge is recognizing that many Collatz sequences overlap and can be optimized using memoization instead of recomputing every step for every number.
Sort Integers by The Power Value Python/Java solution
In Python or Java, iterate from lo to hi, compute each number's power using a loop that follows the Collatz rules, and cache results in a dictionary or HashMap. Store (power, value) pairs in a list, sort them, and return the element at index k-1.
How to solve Sort Integers by The Power Value in O(n)?
Pure O(n) is difficult because the problem requires sorting by power value. The closest practical solution is computing powers with memoization and then sorting, which results in O(n log n) time. Memoization reduces repeated Collatz calculations and keeps the preprocessing step close to linear.
What is the best approach for Sort Integers by The Power Value?
Memoization with sorting is the most efficient approach. Compute the Collatz power value for each integer while caching intermediate results in a hash map. This avoids recalculating power values for numbers that appear multiple times in sequences. After computing powers, sort the integers by (power, value) and return the k-th element.
Is Sort Integers by The Power Value asked at Google/Amazon/Meta?
This problem is tagged as a medium-level algorithm question and appears in coding interview preparation lists for companies like Amazon and Google. It tests knowledge of sorting, memoization, and recognizing repeated subproblems in sequences like the Collatz transformation.
What data structure is used in Sort Integers by The Power Value?
A hash map (dictionary) is commonly used to store memoized power values for intermediate numbers in the Collatz sequence. An array or list stores pairs of (power, integer) which are then sorted using a standard sorting algorithm.
What is the time complexity of Sort Integers by The Power Value?
The optimized solution runs in O(n log n) time where n = hi - lo + 1. Sorting the numbers dominates the runtime, while memoization ensures each power value is computed only once. Space complexity is O(n) for storing power values and the memoization cache.

Ready to solve this problem?

Practice Sort Integers by The Power Value with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Score of an Array After Marking All Elements