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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5

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

Solution

Method 1 - Memoization with Sorting

Intuition

Calculate the power (Collatz conjecture steps) for each number in the range using memoization to avoid recomputation, then sort by power value with number as tiebreaker.

Approach

  1. Use memoization to cache power values to avoid recalculating
  2. For each number in range [lo, hi], calculate its power value
  3. Create pairs of (number, power) and sort by power first, then by number
  4. Return the k-th element (1-indexed)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;

class Solution {
private:
    unordered_map<int, int> memo;
    
    int getPower(int x) {
        if (x == 1) return 0;
        if (memo.find(x) != memo.end()) return memo[x];
        
        int original = x;
        int steps = 0;
        
        while (x != 1 && memo.find(x) == memo.end()) {
            if (x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
            steps++;
        }
        
        // x is either 1 or found in memo
        int totalSteps = steps + (x == 1 ? 0 : memo[x]);
        
        // Backtrack and memoize
        x = original;
        for (int i = steps; i > 0; i--) {
            memo[x] = totalSteps - (steps - i);
            if (x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
        }
        
        return memo[original];
    }
    
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> nums;
        
        for (int i = lo; i <= hi; i++) {
            nums.push_back({getPower(i), i});
        }
        
        sort(nums.begin(), nums.end());
        return nums[k - 1].second;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

func getKth(lo int, hi int, k int) int {
    memo := make(map[int]int)
    
    var getPower func(int) int
    getPower = func(x int) int {
        if x == 1 {
            return 0
        }
        if val, exists := memo[x]; exists {
            return val
        }
        
        original := x
        steps := 0
        
        for x != 1 {
            if _, exists := memo[x]; exists {
                break
            }
            if x%2 == 0 {
                x = x / 2
            } else {
                x = 3*x + 1
            }
            steps++
        }
        
        totalSteps := steps
        if x != 1 {
            totalSteps += memo[x]
        }
        
        // Backtrack and memoize
        x = original
        for i := steps; i > 0; i-- {
            memo[x] = totalSteps - (steps - i)
            if x%2 == 0 {
                x = x / 2
            } else {
                x = 3*x + 1
            }
        }
        
        return memo[original]
    }
    
    type pair struct {
        power int
        num   int
    }
    
    var nums []pair
    for i := lo; i <= hi; i++ {
        nums = append(nums, pair{getPower(i), i})
    }
    
    sort.Slice(nums, func(i, j int) bool {
        if nums[i].power == nums[j].power {
            return nums[i].num < nums[j].num
        }
        return nums[i].power < nums[j].power
    })
    
    return nums[k-1].num
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import java.util.*;

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();
    
    private int getPower(int x) {
        if (x == 1) return 0;
        if (memo.containsKey(x)) return memo.get(x);
        
        int original = x;
        int steps = 0;
        
        while (x != 1 && !memo.containsKey(x)) {
            if (x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
            steps++;
        }
        
        int totalSteps = steps + (x == 1 ? 0 : memo.get(x));
        
        // Backtrack and memoize
        x = original;
        for (int i = steps; i > 0; i--) {
            memo.put(x, totalSteps - (steps - i));
            if (x % 2 == 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
        }
        
        return memo.get(original);
    }
    
    public int getKth(int lo, int hi, int k) {
        List<int[]> nums = new ArrayList<>();
        
        for (int i = lo; i <= hi; i++) {
            nums.add(new int[]{getPower(i), i});
        }
        
        nums.sort((a, b) -> {
            if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[0], b[0]);
        });
        
        return nums.get(k - 1)[1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution {
    private val memo = mutableMapOf<Int, Int>()
    
    private fun getPower(x: Int): Int {
        if (x == 1) return 0
        if (memo.containsKey(x)) return memo[x]!!
        
        val original = x
        var current = x
        var steps = 0
        
        while (current != 1 && !memo.containsKey(current)) {
            current = if (current % 2 == 0) {
                current / 2
            } else {
                3 * current + 1
            }
            steps++
        }
        
        val totalSteps = steps + if (current == 1) 0 else memo[current]!!
        
        // Backtrack and memoize
        current = original
        for (i in steps downTo 1) {
            memo[current] = totalSteps - (steps - i)
            current = if (current % 2 == 0) {
                current / 2
            } else {
                3 * current + 1
            }
        }
        
        return memo[original]!!
    }
    
    fun getKth(lo: Int, hi: Int, k: Int): Int {
        val nums = mutableListOf<Pair<Int, Int>>()
        
        for (i in lo..hi) {
            nums.add(Pair(getPower(i), i))
        }
        
        nums.sortWith { a, b ->
            when {
                a.first != b.first -> a.first.compareTo(b.first)
                else -> a.second.compareTo(b.second)
            }
        }
        
        return nums[k - 1].second
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def getKth(lo: int, hi: int, k: int) -> int:
    memo = {}
    
    def get_power(x):
        if x == 1:
            return 0
        if x in memo:
            return memo[x]
        
        original = x
        steps = 0
        
        while x != 1 and x not in memo:
            if x % 2 == 0:
                x = x // 2
            else:
                x = 3 * x + 1
            steps += 1
        
        total_steps = steps + (0 if x == 1 else memo[x])
        
        # Backtrack and memoize
        x = original
        for i in range(steps, 0, -1):
            memo[x] = total_steps - (steps - i)
            if x % 2 == 0:
                x = x // 2
            else:
                x = 3 * x + 1
        
        return memo[original]
    
    nums = []
    for i in range(lo, hi + 1):
        nums.append((get_power(i), i))
    
    nums.sort()
    return nums[k - 1][1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

use std::collections::HashMap;

pub fn get_kth(lo: i32, hi: i32, k: i32) -> i32 {
    let mut memo: HashMap<i32, i32> = HashMap::new();
    
    fn get_power(x: i32, memo: &mut HashMap<i32, i32>) -> i32 {
        if x == 1 {
            return 0;
        }
        if let Some(&power) = memo.get(&x) {
            return power;
        }
        
        let original = x;
        let mut current = x;
        let mut steps = 0;
        
        while current != 1 && !memo.contains_key(&current) {
            if current % 2 == 0 {
                current = current / 2;
            } else {
                current = 3 * current + 1;
            }
            steps += 1;
        }
        
        let total_steps = steps + if current == 1 { 0 } else { memo[&current] };
        
        // Backtrack and memoize
        current = original;
        for i in (1..=steps).rev() {
            memo.insert(current, total_steps - (steps - i));
            if current % 2 == 0 {
                current = current / 2;
            } else {
                current = 3 * current + 1;
            }
        }
        
        memo[&original]
    }
    
    let mut nums = Vec::new();
    for i in lo..=hi {
        nums.push((get_power(i, &mut memo), i));
    }
    
    nums.sort();
    nums[(k - 1) as usize].1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

function getKth(lo: number, hi: number, k: number): number {
    const memo = new Map<number, number>();
    
    function getPower(x: number): number {
        if (x === 1) return 0;
        if (memo.has(x)) return memo.get(x)!;
        
        const original = x;
        let current = x;
        let steps = 0;
        
        while (current !== 1 && !memo.has(current)) {
            if (current % 2 === 0) {
                current = current / 2;
            } else {
                current = 3 * current + 1;
            }
            steps++;
        }
        
        const totalSteps = steps + (current === 1 ? 0 : memo.get(current)!);
        
        // Backtrack and memoize
        current = original;
        for (let i = steps; i > 0; i--) {
            memo.set(current, totalSteps - (steps - i));
            if (current % 2 === 0) {
                current = current / 2;
            } else {
                current = 3 * current + 1;
            }
        }
        
        return memo.get(original)!;
    }
    
    const nums: [number, number][] = [];
    for (let i = lo; i <= hi; i++) {
        nums.push([getPower(i), i]);
    }
    
    nums.sort((a, b) => {
        if (a[0] === b[0]) return a[1] - b[1];
        return a[0] - b[0];
    });
    
    return nums[k - 1][1];
}

Complexity

  • ⏰ Time complexity: O(n * m + n log n) where n = hi - lo + 1 (range size), m = average steps for Collatz sequence
  • 🧺 Space complexity: O(n + cache_size) for storing pairs and memoization cache