Dynamic Programming (Memoization) to Sort Integers by The Power Value

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 k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x &lt= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 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 = 1, hi = 1, k = 1
Output: 1

Example 3:
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.

Example 4:
Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:
Input: lo = 1, hi = 1000, k = 777
Output: 570

Constraints:
1 <= lo <= hi <= 1000
1 <= k <= hi – lo + 1

Hints:
Use dynamic programming to get the power of each integer of the intervals.
Sort all the integers of the interval by the power value and return the k-th in the sorted list.

Standard Iterative Approach with Custom Sorting Algorithm

The first thought is to iterate all numbers between the given range, then calculate their power using a iterative approach. Next perform a custom sorting and return the corresponding number.

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

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> r;
        for (int i = lo; i <= hi; ++ i) {
            r.push_back({i, getSteps(i)});
        }
        sort(begin(r), end(r), [](auto &a, auto &b) {
            if (a.second < b.second) return true;
            if (a.second > b.second) return false;
            return a.first < b.first;
        });
        return r[k - 1].first;
    }
private:
    int getSteps(int n) {
        int r = 0;
        while (n != 1) {
            r ++;
            if (n & 1) {
                n = 3 * n + 1;
            } else {
                n /= 2;
            }
        }
        return r;
    }
};

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> r;
        for (int i = lo; i <= hi; ++ i) {
            r.push_back({i, getSteps(i)});
        }
        sort(begin(r), end(r), [](auto &a, auto &b) {
            if (a.second < b.second) return true;
            if (a.second > b.second) return false;
            return a.first < b.first;
        });
        return r[k - 1].first;
    }
private:
    int getSteps(int n) {
        int r = 0;
        while (n != 1) {
            r ++;
            if (n & 1) {
                n = 3 * n + 1;
            } else {
                n /= 2;
            }
        }
        return r;
    }
};

Can we do better? We can swap the the pair in the array, thus, we just need to sort them without the custom comparator.

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> r;
        for (int i = lo; i <= hi; ++ i) {
            r.push_back({getSteps(i), i});
        }
        sort(begin(r), end(r));
        return r[k - 1].second;               
    }
}

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> r;
        for (int i = lo; i <= hi; ++ i) {
            r.push_back({getSteps(i), i});
        }
        sort(begin(r), end(r));
        return r[k - 1].second;               
    }
}

Dynamic Programming (Memoization) to Compute the Power of Integers

With the Dynamic Programming technique, we can compute the Power for the Integers using Recursion with Memoization. This requires O(N) space though.

1
2
3
4
5
6
7
8
9
10
11
12
13

private:
    unordered_map<int, int> memo;
    
    int getSteps(int n) {
        if (n == 1) return 0;
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        if (n & 1) {
            return 1 + getSteps(3 * n + 1);
        }
        return 1 + getSteps(n / 2);
    }

private:
    unordered_map<int, int> memo;
    
    int getSteps(int n) {
        if (n == 1) return 0;
        if (memo.find(n) != memo.end()) {
            return memo[n];
        }
        if (n & 1) {
            return 1 + getSteps(3 * n + 1);
        }
        return 1 + getSteps(n / 2);
    }

–EOF (The Ultimate Computing & Technology Blog) —