Minimum Array End - Video Solutions

Problem Overview: You need to build an increasing array of size n where the bitwise AND of all elements equals x. The goal is to keep the array valid while making the last element as small as possible.

Approach 1: Incremental Construction (O(n) time, O(1) space)

Start the array with arr[0] = x. For every next element, increment the previous value until the condition (value & x) == x holds. This guarantees every number keeps all bits that appear in x, so the AND of the entire array never drops below x. In practice you compute the next value using next = (prev + 1) | x, which forces required bits back to 1. Repeat this process n-1 times until the array reaches size n. The approach is simple and intuitive because it directly simulates building the array while maintaining the constraint. Time complexity is O(n) since each step computes the next valid value, and space complexity is O(1). This approach relies heavily on operations from bit manipulation.

Approach 2: Binary Manipulation (O(log n) time, O(1) space)

The key observation is that every element must contain all the set bits of x. The only freedom comes from the bit positions where x has 0. Instead of constructing the array explicitly, encode the sequence growth directly into those zero-bit positions. Let k = n - 1. Traverse the bits of x from least significant to most significant. Whenever a bit in x is 0, take the next bit from k and place it into that position. If the bit in x is already 1, keep it unchanged. This effectively distributes the binary representation of n-1 across the available zero positions of x, producing the smallest possible final number while maintaining the AND constraint. The algorithm runs in O(log n) time because you process each bit once, and uses O(1) extra space. This technique is a classic pattern in bit manipulation and bitmask problems where unused bit positions encode additional state.

Recommended for interviews: The binary manipulation approach is what most interviewers expect. It shows you understand how bit constraints propagate across numbers and how to encode sequence indices inside unused bits. The incremental construction method still helps demonstrate the underlying rule ((value & x) == x), but the optimized bit mapping solution proves stronger problem-solving skills.