4059. Lexicographically Largest Power Array (Leetcode Hard)
Lexicographically Largest Power Array - Video Solution
Watch 2 video solutions for Lexicographically Largest Power Array, a hard level problem. This walkthrough by Programming Live with Larry has 350 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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].
- Both elements have bit 2 set, so
power[12] = 2. - The first element has bit 1 set, but the second does not, so
power[13] = 1. - Both elements have bit 0 set, so
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].
- The first element has bit 2 set, but the second does not, so
power[12] = 1. - The first two elements have bit 1 set, but the third does not, so
power[13] = 2. - All three elements have bit 0 set, so
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] < 215