Sort Integers by The Power Value - Practice Coding Problems

Sort Integers by The Power Value - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: lo = 7, hi = 11, k = 4

› Output: 7

💡 Note: Powers: 7→16, 8→3, 9→19, 10→6, 11→14. Sorted by power: [8,10,11,7,9]. 4th element is 7.

Example 2 — Small Range

$ Input: lo = 10, hi = 20, k = 5

› Output: 13

💡 Note: Calculate power for each number 10-20, sort by power values, return 5th element.

Example 3 — Single Element

$ Input: lo = 1, hi = 1, k = 1

› Output: 1

💡 Note: Only one number in range [1,1], so return 1 (power of 1 is 0).

Constraints

1 ≤ lo ≤ hi ≤ 1000
1 ≤ k ≤ hi - lo + 1

Visualization

Tap to expand

Understanding the Visualization

Input Range

Numbers in range [lo, hi] with target position k

Calculate Powers

Apply Collatz conjecture rules to find power of each number

Sort & Select

Sort by power values, return kth element

Key Takeaway

🎯 Key Insight: Use memoization to cache power calculations since transformation sequences often overlap

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use memoization to cache power calculations since many numbers share transformation paths. Calculate power for each number using Collatz conjecture rules, sort by power (then by value for ties), and return kth element. Best approach uses memoization. Time: O(n log n + unique_paths), Space: O(n + cache_size)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization - Cache Power Calculations	O(n log n + unique_paths)	O(n + cache_size)	Cache power calculations to avoid redundant computation for overlapping sequences
Brute Force - Direct Calculation	O(n log n + n*m)	O(n)	Calculate power for each number directly, then sort and return kth element

Memoization - Cache Power Calculations — Algorithm Steps

Create memo map for caching
For each number, check cache first
Calculate power recursively with memoization
Sort results and return kth element

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate & Cache

Calculate power for first number, store in memo

Reuse Cache

For subsequent numbers, check cache first

Sort & Select

Sort by cached powers and return kth element

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

#define MAX_CACHE 100000

typedef struct {
    int num;
    int power;
} NumberPower;

static int cache[MAX_CACHE];
static int cache_initialized = 0;

void init_cache() {
    if (!cache_initialized) {
        for (int i = 0; i < MAX_CACHE; i++) {
            cache[i] = -1;
        }
        cache_initialized = 1;
    }
}

int getPower(int x) {
    init_cache();
    
    if (x < MAX_CACHE && cache[x] != -1) {
        return cache[x];
    }
    
    int original = x;
    int steps = 0;
    
    while (x != 1) {
        if (x < MAX_CACHE && cache[x] != -1) {
            steps += cache[x];
            break;
        }
        
        if (x % 2 == 0) {
            x = x / 2;
        } else {
            x = 3 * x + 1;
        }
        steps++;
    }
    
    if (original < MAX_CACHE) {
        cache[original] = steps;
    }
    return steps;
}

int compare(const void *a, const void *b) {
    NumberPower *na = (NumberPower *)a;
    NumberPower *nb = (NumberPower *)b;
    if (na->power != nb->power) {
        return na->power - nb->power;
    }
    return na->num - nb->num;
}

int solution(int lo, int hi, int k) {
    int size = hi - lo + 1;
    NumberPower *numbers = malloc(size * sizeof(NumberPower));
    
    // Calculate power for each number
    for (int i = 0; i < size; i++) {
        int num = lo + i;
        numbers[i].num = num;
        numbers[i].power = getPower(num);
    }
    
    // Sort by power, then by number value
    qsort(numbers, size, sizeof(NumberPower), compare);
    
    // Get kth element (1-indexed)
    int result = numbers[k - 1].num;
    free(numbers);
    return result;
}

int main() {
    int lo, hi, k;
    scanf("%d %d %d", &lo, &hi, &k);
    
    int result = solution(lo, hi, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + unique_paths)

Unique power calculations amortized across all numbers, plus O(n log n) sorting

⚡ Linearithmic

Space Complexity

O(n + cache_size)

Array for results plus memoization cache for power calculations

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization - Cache Power Calculations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler