|
4 | 4 | importjava.util.Collections; |
5 | 5 | importjava.util.List; |
6 | 6 |
|
7 | | -/** |
8 | | - * 1387. Sort Integers by The Power Value |
9 | | - * |
10 | | - * The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps: |
11 | | - * if x is even then x = x / 2 |
12 | | - * if x is odd then x = 3 * x + 1 |
13 | | - * |
14 | | - * 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). |
15 | | - * 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. |
16 | | - * Return the k-th integer in the range [lo, hi] sorted by the power value. |
17 | | - * 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. |
18 | | - * |
19 | | - * Example 1: |
20 | | - * Input: lo = 12, hi = 15, k = 2 |
21 | | - * Output: 13 |
22 | | - * Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1) |
23 | | - * The power of 13 is 9 |
24 | | - * The power of 14 is 17 |
25 | | - * The power of 15 is 17 |
26 | | - * The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13. |
27 | | - * Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15. |
28 | | - * |
29 | | - * Example 2: |
30 | | - * Input: lo = 1, hi = 1, k = 1 |
31 | | - * Output: 1 |
32 | | - * |
33 | | - * Example 3: |
34 | | - * Input: lo = 7, hi = 11, k = 4 |
35 | | - * Output: 7 |
36 | | - * Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14]. |
37 | | - * The interval sorted by power is [8, 10, 11, 7, 9]. |
38 | | - * The fourth number in the sorted array is 7. |
39 | | - * |
40 | | - * Example 4: |
41 | | - * Input: lo = 10, hi = 20, k = 5 |
42 | | - * Output: 13 |
43 | | - * |
44 | | - * Example 5: |
45 | | - * Input: lo = 1, hi = 1000, k = 777 |
46 | | - * Output: 570 |
47 | | - * |
48 | | - * Constraints: |
49 | | - * 1 <= lo <= hi <= 1000 |
50 | | - * 1 <= k <= hi - lo + 1 |
51 | | - * */ |
52 | 7 | publicclass_1387 { |
53 | 8 | publicstaticclassSolution1 { |
54 | 9 | publicintgetKth(intlo,inthi,intk) { |
|