We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Array End

Number: 3394

Difficulty: Medium

Paid? No

Companies: Google, Meta, Bloomberg

Problem Description

Given two integers n and x, construct an array nums of n positive integers in strictly increasing order (i.e. for every i from 0 to n – 2, nums[i+1] > nums[i]) such that the bitwise AND of all elements in nums is exactly x. Return the minimum possible value of nums[n – 1] (the last element).

Recall that the bitwise AND of several numbers returns a number which has a 1 in each bit position only if every one of the numbers has a 1 in that position. Thus, for the AND of the entire array to be x, every element must have all the bits that appear as 1’s in x. However, any extra bit that gets “turned on” in every element would force that bit in the overall AND, so those extra bits must be “distributed” – not present in every element.

For example: • For n = 3 and x = 4 (binary 100), one valid array is [4, 5, 6]:  – 4 = 100, 5 = 101, 6 = 110.  – They are strictly increasing and 4 & 5 & 6 = 100 (i.e. 4). • For n = 2 and x = 7 (binary 111), one valid array is [7, 15]:  – 7 = 0111 and 15 = 1111, with AND = 0111 (i.e. 7).

Key Insights

  • Every element must have all the “fixed” bits that appear in x.
  • In order for the overall AND to remain exactly x, any extra (non‑x) bit that appears in one or more elements must not appear in every element.
  • We can “encode” differences from x by choosing some extra bits (taken only from positions where x has a 0) and assign them to some of the n – 1 remaining elements.
  • There is a natural mapping from selecting extra bits to forming numbers. In fact, if we can “simulate” all numbers of the form x OR t (where t is a bitmask over some candidate extra bits), then the candidate t=0 gives x and the maximum (when t is chosen as some particular number) will be x plus the sum of certain selected candidate extra bits.
  • To minimize the maximum element, we select the smallest candidate extra bits – that is, the lowest positions where x is 0.
  • Note that if we have a chosen set of k candidate extra bits then there are 2^(k) possible numbers of the form x OR t. If we can “cover” at least n distinct numbers then we can pick an increasing sequence where the maximum is exactly x plus a sum corresponding to one of those t values.
  • By carefully “allocating” extra bits to only some of the numbers, a clever observation is that the minimum maximum is given by x plus a number that encodes n – 1 (when written in binary) mapped onto the k smallest bit positions (with x=0) – where k is the minimum number such that 2^(k) is at least n.

Space and Time Complexity

Time Complexity: O(k) where k is the number of candidate extra bits used (in practice k is bounded by the number of bits needed, e.g. around 32 or so).
Space Complexity: O(k) for storing the candidate bits.

Solution

The key observation is to “build” the n numbers as x OR t, where t is chosen from subsets of a set of candidate extra bits. To avoid adding any extra bit to the overall AND, it must be absent from at least one number. Notice that if we choose the first element as x (i.e. t = 0) then this number “cancels” any candidate extra bit that might be forced if applied to every element.

Given that we need n distinct numbers, one can see that if we have k candidate extra bits (each coming from a position where x is 0), we can form up to 2^k distinct numbers. To “just cover” n numbers while keeping the maximum as small as possible, choose the smallest k such that 2^k >= n. Then among these 2^k possibilities, we want to choose n numbers so that the maximum element is minimized. A natural greedy approach is to assign to the maximum element the candidate extra bits corresponding to the binary representation of (n – 1) using the selected candidate bits in increasing order. Therefore, the answer becomes:

  answer = x + (∑ over i of (bit i of (n – 1)) * (2^(p_i)))

where p_i are the positions (in increasing order) of bits that are 0 in x. (In other words, we scan the bit positions from low to high, pick those that are 0 in x, and take the first k candidates. Then, writing (n – 1) in binary using k bits, for every “1” in this representation we add the corresponding candidate bit (which is just a power of 2) to x.)

For example, when n = 3 and x = 4:
 x = 4, binary 100.
 Candidate extra bits (positions where x has 0) in increasing order are: 2^0 = 1 and 2^1 = 2.
 k = ceil(log2(3)) = 2.
 Now n – 1 = 2 is binary “10”. This tells us not to use the candidate 1 but to use the candidate 2.
 Thus, answer = 4 + 2 = 6.

When n = 2 and x = 7:
 x = 7, binary 111.
 The first candidate extra bit is 2^3 = 8 (since bits 0,1,2 are already 1 in x).
 n – 1 = 1 (binary “1”), so we add 8 giving answer = 7 + 8 = 15.

This approach efficiently finds the answer with a neat mapping from the number of extra elements (n – 1) to the extra bits chosen.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with explanatory comments.

# Python solution for Minimum Array End

def minimumArrayEnd(n, x):
    # When n == 1, we only have one number which is x.
    if n == 1:
        return x

    # Determine the minimum k such that 2^k >= n.
    k = 0
    while (1 << k) < n:
        k += 1

    # Build candidate extra bits: list the lowest k powers of 2 corresponding
    # to bit positions where x has a 0.
    candidates = []
    pos = 0
    # Because x < 10^8, and n is at most 1e8,
    # there will always be enough 0 bits in the range we search.
    while len(candidates) < k:
        # if the bit at position pos is not set in x, add it as a candidate.
        if not (x & (1 << pos)):
            candidates.append(1 << pos)
        pos += 1

    # Map the binary representation of n - 1 onto the candidate bits.
    extra_val = 0
    for i in range(k):
        if (n - 1) & (1 << i):
            extra_val += candidates[i]

    # The answer is x plus the extra bits needed for the maximum element.
    return x + extra_val

# Example usage:
print(minimumArrayEnd(3, 4))  # Expected output: 6
print(minimumArrayEnd(2, 7))  # Expected output: 15
← Back to All Questions