Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1387.html
1387. Sort Integers by The Power Value (Medium)
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 thenx = x / 2
- if
x
is odd thenx = 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 <= 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
Solution 1.
-
class Solution { public int getKth(int lo, int hi, int k) { int length = hi - lo + 1; int[][] array = new int[length][2]; for (int i = 0; i < length; i++) { array[i][0] = lo + i; array[i][1] = getPower(lo + i); } Arrays.sort(array, new Comparator<int[]>() { public int compare(int[] element1, int[] element2) { if (element1[1] != element2[1]) return element1[1] - element2[1]; else return element1[0] - element2[0]; } }); return array[k - 1][0]; } public int getPower(int num) { int power = 0; while (num != 1) { if (num % 2 == 0) num /= 2; else num = 3 * num + 1; power++; } return power; } }
-
// OJ: https://leetcode.com/problems/sort-integers-by-the-power-value/ // Time: O(NlogN) // Space: O(N) class Solution { int power(int x) { int ans = 0; while (x != 1) { if (x % 2) x = x * 3 + 1; else x /= 2; ++ans; } return ans; } public: int getKth(int lo, int hi, int k) { vector<pair<int, int>> v; for (int i = lo; i <= hi; ++i) v.emplace_back(power(i), i); sort(v.begin(), v.end()); return v[k - 1].second; } };
-
@cache def f(x: int) -> int: ans = 0 while x != 1: if x % 2 == 0: x //= 2 else: x = 3 * x + 1 ans += 1 return ans class Solution: def getKth(self, lo: int, hi: int, k: int) -> int: return sorted(range(lo, hi + 1), key=f)[k - 1]
-
func getKth(lo int, hi int, k int) int { f := func(x int) (ans int) { for ; x != 1; ans++ { if x%2 == 0 { x /= 2 } else { x = 3*x + 1 } } return } nums := make([]int, hi-lo+1) for i := range nums { nums[i] = lo + i } sort.Slice(nums, func(i, j int) bool { fx, fy := f(nums[i]), f(nums[j]) if fx != fy { return fx < fy } return nums[i] < nums[j] }) return nums[k-1] }
-
function getKth(lo: number, hi: number, k: number): number { const f = (x: number): number => { let ans = 0; for (; x !== 1; ++ans) { if (x % 2 === 0) { x >>= 1; } else { x = x * 3 + 1; } } return ans; }; const nums = new Array(hi - lo + 1).fill(0).map((_, i) => i + lo); nums.sort((a, b) => { const fa = f(a), fb = f(b); return fa === fb ? a - b : fa - fb; }); return nums[k - 1]; }