You are given an integer array nums of length n. You may rearrange its elements to form any permutation perm.
Define an array power of length 15. For each 0 <= i < 15, power[i] is the largest integer j, where 0 <= j <= n, such that the first j elements of perm all have the (14 - i)th bit set.
Bit positions are indexed from right to left, starting with the 0th bit.
Return the lexicographically largest possible power array.
Example 1:
Input: nums = [7,5]
Output: [0,0,0,0,0,0,0,0,0,0,0,0,2,1,2]
Explanation:
Choose perm = [7, 5].
power[12] = 2.power[13] = 1.power[14] = 2.All higher bits are unset in the first element, so the remaining entries are 0.
Example 2:
Input: nums = [3,1,7]
Output: [0,0,0,0,0,0,0,0,0,0,0,0,1,2,3]
Explanation:
Choose perm = [7, 3, 1].
power[12] = 1.power[13] = 2.power[14] = 3.All higher bits are unset in the first element, so the remaining entries are 0.
Constraints:
1 <= nums.length <= 5 * 1040 <= nums[i] < 215Process bits from 14 down to 0, maximizing each entry without changing previously maximized entries. Maintain ordered groups of elements that can still be rearranged freely within each group. Initially, all elements belong to one group.
For the current bit, scan the groups from the beginning. Pass over groups whose elements all have this bit set. At the first group containing an element without this bit set, split it into elements with the bit set followed by elements without it. Stop there and leave all later groups unchanged.
The current entry of power equals the total size of the fully passed groups plus the number of elements with the bit set in the split group. Preserve the resulting group order for subsequent bits. This takes O(15n) time.
[7,5]
[3,1,7]