lexicographically-largest-power-array

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code>. You may rearrange its elements to form any permutation <code>perm</code>.

Define an array <code>power</code> of length 15. For each <code>0 &lt;= i &lt; 15</code>, <code>power[i]</code> is the largest integer <code>j</code>, where <code>0 &lt;= j &lt;= n</code>, such that the first <code>j</code> elements of <code>perm</code> all have the <code>(14 - i)th</code> bit set.

Bit positions are indexed from right to left, starting with the <code>0th</code> bit.

Return the lexicographically largest possible <code>power</code> array.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [7,5]

Output: [0,0,0,0,0,0,0,0,0,0,0,0,2,1,2]

Explanation:

Choose <code>perm = [7, 5]</code>.

<ul>
	<li>Both elements have bit 2 set, so <code>power[12] = 2</code>.</li>
	<li>The first element has bit 1 set, but the second does not, so <code>power[13] = 1</code>.</li>
	<li>Both elements have bit 0 set, so <code>power[14] = 2</code>.</li>
</ul>

All higher bits are unset in the first element, so the remaining entries are 0.
</div>

Example 2:

<div class="example-block">
Input: nums = [3,1,7]

Output: [0,0,0,0,0,0,0,0,0,0,0,0,1,2,3]

Explanation:

Choose <code>perm = [7, 3, 1]</code>.

<ul>
	<li>The first element has bit 2 set, but the second does not, so <code>power[12] = 1</code>.</li>
	<li>The first two elements have bit 1 set, but the third does not, so <code>power[13] = 2</code>.</li>
	<li>All three elements have bit 0 set, so <code>power[14] = 3</code>.</li>
</ul>

All higher bits are unset in the first element, so the remaining entries are 0.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 104</code></li>
	<li><code>0 &lt;= nums[i] &lt; 215</code></li>
</ul>