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>

Weekly Contest 520

weekly-contest-520

largestPower

Principal

Lexicographically Largest Power Array

Array

Greedy

Bit Manipulation

Accepted

Wrong Answer

Memory Limit Exceeded

Output Limit Exceeded

Time Limit Exceeded

Runtime Error

Internal Error

Compile Error

Timeout

Restrictions Failed

cangjie

react

vanillajs

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