Skip to main content
Talentd

Lexicographically Largest Power Array - Solution & Explanation

Hard2 min read
Practice this problem

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 * 104
  • 0 <= nums[i] < 215

Solutions for this problem are being prepared.

Try solving it yourself

Video Solution

4059. Lexicographically Largest Power Array (Leetcode Hard) • Programming Live with Larry • 350 views views

Watch 1 more video solutions →

Ready to solve this problem?

Practice Lexicographically Largest Power Array with our built-in code editor and test cases.

Practice on FleetCode