⚡Flashcard Drill➔
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

  1. For the AND of the whole array to be x, every element must contain all the set bits of x; the remaining freedom lives in the zero-bits of x.
  2. The smallest possible array starts at x and uses the zero-bit positions of x as a counter, so there are n - 1 increments to distribute.
  3. Pack the binary representation of n - 1 into the free bit positions of x, from least significant upwards, preserving their relative order.
  4. 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 of x are free; for n = 2, x = 7 the answer is 15, not 7.
  • Using n instead of n - 1: the array starts at x, so only n - 1 increments remain to be placed.
  • Packing the offset bits in the wrong order: the bits of n - 1 must fill the free positions from low to high, not be OR-ed wholesale.
  • Assuming x has enough free bits below 32: n, x <= 10^8 keeps 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.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems