Skip to main content
Talentd

Minimum Array End - Solution & Explanation

MediumBit Manipulation16 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

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 <= 108

Approach Overview

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.

Approach 1: Approach 1: Incremental Construction

In this approach, we begin by constructing an array where each element is initialized to the given value of x. We then increment each subsequent element by 1 ensuring that it is greater than the previous element. We stop when we've constructed an array of size n.

This works because the bitwise AND of all numbers will still be x, since all elements are derived from x and only the last element needs to change significantly to ensure uniqueness and satisfy the increasing property.

The function calculates the minimum possible value of the last element by starting with x and incrementing it by n - 1 to ensure all previous n-1 elements are strictly increasing starting from x.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Approach 2: Binary Manipulation

In this approach, we consider constructing the array by leveraging the bitwise properties to ensure the AND operation returns x. We create the first n-1 elements as numbers starting from x incrementally, and ensure the last element is the smallest number fitting the need for bitwise AND to be x.

To optimize the last number's structure, we can explore modifying bits in consideration of the upcoming elements and control zeroed bits strategically to adjust value and ensure valid returns upon AND calculation.

This C code uses bit manipulation to construct the minimum end element. By setting the suitable bits, we obtain potential n-1 lower bits set to create a higher value that preserves higher x values, exploiting AND product properties.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Greedy + Bit Manipulation

According to the problem description, to make the last element of the array as small as possible and the bitwise AND result of the elements in the array is x, the first element of the array must be x.

Assume the binary representation of x is \underline{1}00\underline{1}00, then the array sequence is \underline{1}00\underline{1}00, \underline{1}00\underline{1}01, \underline{1}00\underline{1}10, \underline{1}00\underline{1}11...

If we ignore the underlined part, then the array sequence is 0000, 0001, 0010, 0011..., the first item is 0, then the n-th item is n-1.

Therefore, the answer is to fill each bit of the binary of n-1 into the 0 bit of the binary of x based on x.

The time complexity is O(log x), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Incremental Construction

Time Complexity: O(1)
Space Complexity: O(1)

Approach 2: Binary Manipulation

Time Complexity: O(n)
Space Complexity: O(1)

Greedy + Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Incremental ConstructionO(n)O(1)Good for understanding the constraint and simulating the array step by step
Binary ManipulationO(log n)O(1)Best for large n and interviews; computes the final value directly

Video Solution

Minimum Array End - Leetcode 3133 - Python • NeetCodeIO • 14,264 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Array End with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary