Is Minimum Array End easy or hard?

Minimum Array End is rated Medium because the key insight about mapping n-1 into the zero bits of x is not immediately obvious. Once the bit manipulation pattern is recognized, the implementation becomes short and efficient.

Minimum Array End Python/Java solution

In Python or Java, the optimal solution iterates through the bits of x and fills zero positions with bits from n-1 using shifts and bitwise OR operations. The logic is identical across languages and runs in O(log n) time with constant space.

How to solve Minimum Array End in O(log n)?

Compute k = n - 1 and treat it as a binary number that fills the zero-bit positions of x. Iterate through the bit positions of x from least significant upward. Whenever a bit in x is 0, place the next bit of k there. The resulting number is the minimal possible array end.

What is the best approach for Minimum Array End?

The binary manipulation approach is the most efficient. It distributes the bits of n-1 into the zero-bit positions of x to construct the smallest valid final element. This avoids building the entire array and runs in O(log n) time with O(1) extra space.

Is Minimum Array End asked at Google/Amazon/Meta?

Problems involving bit manipulation and bitmask construction appear frequently in interviews at companies like Google, Amazon, and Meta. While this exact question may vary, the underlying technique of embedding values into unused bit positions is a common interview pattern.

What data structure is used in Minimum Array End?

The problem primarily uses bit manipulation rather than traditional data structures. Operations like bit masking, shifting, and checking individual bits are used to construct the final number efficiently.

What is the time complexity of Minimum Array End?

The optimal solution runs in O(log n) time because it processes the binary representation of n-1 and the bit positions of x. A simpler incremental construction approach exists but takes O(n) time since it generates each element sequentially.

Description Hints 3 Solution Video 23:22

3133. Minimum Array End

Medium55.5% acceptance4 companies

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.

Constraints:

1 <= n, x <= 10⁸

Asked at 4 companies

Google Amazon Meta Bloomberg

Topics

Bit Manipulation

Hints open one at a time

Hint 1

Each element of the array should be obtained by “merging” x and v where v = 0, 1, 2, …(n - 1).

Hint 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.

Hint 3

So the final answer is the “merge” of x and n - 1.

23:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minEnd(self, n: int, x: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

3
4

Input

2
7

Your code is saved on this device.Solution