Minimum Array End

3133. Minimum Array End

Difficulty: Medium

Topics: Bit Manipulation

You are given two integers n and x. You have to construct an array of positive integers nums of size n where for every 0 <= i < n - 1, nums[i 1] is greater than nums[i], and the result of the bitwise AND operation between all elements of nums is x.

Return the minimum possible value of nums[n - 1].

Example 1:

• Input: n = 3, x = 4
• Output: 6
• Explanation: nums can be [4,5,6] and its last element is 6.

Example 2:

• Input: n = 2, x = 7
• Output: 15
• Explanation: nums can be [7,15] and its last element is 15.

Example 3:

• Input: cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]
• Output: 10

Constraints:

• 1 <= n, x <= 10⁸

Hint:

1. Each element of the array should be obtained by “merging” x and v where v = 0, 1, 2, …(n - 1).
2. To merge x with another number v, keep the set bits of x untouched, for all the other bits, fill the set bits of v from right to left in order one by one.
3. So the final answer is the “merge” of x and n - 1.

Solution:

We need to construct an array nums of positive integers of size n, where each successive element is greater than the previous. The bitwise AND of all elements in nums should yield x. We are asked to find the minimum possible value of nums[n-1].

Here’s the breakdown:

1. Bit Manipulation Insight: We can observe that nums[i] should be built by merging x with integers 0, 1, ..., n-1. This will help ensure the bitwise AND result yields x since we start with a base of x.

2. Building the Array Elements: Each element can be thought of as x merged with some integer, and we aim to keep x's bits intact. We fill in additional bits from the integer to get increasing numbers while maintaining the AND outcome as x.

3. Merging Strategy: To find the minimum nums[n-1], we only need to merge x with n-1. Merging in this context means that if any bit in x is 1, it remains 1. We use bits from n-1 to add any required additional bits without altering the bits set in x.

Let's implement this solution in PHP: 3133. Minimum Array End

  
  
  説明：




ビットのチェックと設定:


ans の各ビット (x から開始) をチェックし、ans のビットが 0 の場合は、k (n-1) の対応するビットを調べます。
k のビットが 1 の場合、ans のビットを 1 に設定します。このプロセスにより、x に設定されたビットを維持しながら値の最小増分が保証されます。



ループ制約:


計算された最大値 (kMaxBit) まで各ビット位置を反復処理し、x と n の両方から必要なビットを確実にカバーします。



結果:


ans の最終値は、条件を満たす nums[n-1] の最小値です。





  
  
  複雑：



この範囲内の整数のビット数は 32 で制限されるため、アルゴリズムは一定時間で動作し、n と x の値が大きい場合でもこのアプローチは効率的になります。


このソリューションは、必要なプロパティを維持しながら、必要な最小の nums[n-1] を生成します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:


LinkedIn
GitHub



          

            
  

            
        
The above is the detailed content of Minimum Array End. For more information, please follow other related articles on the PHP Chinese website!