NeetCode #874LC-3133MediumBit ManipulationNC 250
← Back to All Problems#874 · #3133 · Minimum Array End(数组最后一个元素的最小值)
📌 Problem Statement & Constraints
Given two integers
n and x, build an array nums of n positive integers such that nums is strictly increasing and the bitwise AND of all its elements equals x. Return the minimum possible value of nums[n - 1]. Constraints: 1 <= n, x <= 10^8.💡 Core Algorithmic Approaches
- For the AND of the whole array to be
x, every element must contain all the set bits ofx; the remaining freedom lives in the zero-bits ofx. - The smallest possible array starts at
xand uses the zero-bit positions ofxas a counter, so there aren - 1increments to distribute. - Pack the binary representation of
n - 1into the free bit positions ofx, from least significant upwards, preserving their relative order. - The resulting number is the smallest possible
nums[n - 1].
💻 Benchmark Python3 Implementation
class Solution:
def minEnd(self, n: int, x: int) -> int:
res = x
k = n - 1 # offset to pack into the free bits of x
bit = 1
while k:
if not (x & bit): # a bit position that x leaves free
if k & 1:
res |= bit
k >>= 1
bit <<= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(log n + log x): a single walk over the bit positions.
💾 Space Complexity
O(1): a few scalars.
⚠️ Interview Pitfalls & Follow-ups
- Returning
x | (n - 1): that only works when the low bits ofxare free; forn = 2, x = 7the answer is 15, not 7. - Using
ninstead ofn - 1: the array starts atx, so onlyn - 1increments remain to be placed. - Packing the offset bits in the wrong order: the bits of
n - 1must fill the free positions from low to high, not be OR-ed wholesale. - Assuming
xhas enough free bits below 32:n, x <= 10^8keeps everything inside 32 bits, but the loop must not stop early.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.