Minimum Array End — Medium Problem & Solution

Problem statement

Build a strictly increasing array of n positive integers whose bitwise AND is exactly x.

Return the smallest possible value of the last element.

Example 1

Input: n = 3, x = 4
Output: 6
Explanation: The array [4,5,6] has AND 4 and ends at 6.

Example 2

Input: n = 2, x = 7
Output: 15
Explanation: [7,15] is the cheapest pair whose AND is 7.

Example 3

Input: n = 1, x = 9
Output: 9
Explanation: A single element is its own AND.

Constraints

• 1 <= n <= 1000
• 1 <= x <= 1000

How to solve Minimum Array End

A value has AND-compatible bits exactly when it is a superset of x. The valid values in increasing order are obtained by writing 0, 1, 2, … into the zero positions of x, so the n-th one embeds n - 1.

Approach

1. Start with result = x and rest = n - 1.
2. Walk bit positions upward. When x has a zero at that position, consume the lowest remaining bit of rest and set it in result if it is 1.
3. Stop once rest is exhausted.

Why it works

Every element must be a superset of x, and the AND of all of them is x as long as each free bit is zero in at least one element — which holds because the first element is x itself. Ordering the supersets by the value packed into the free slots is exactly ordering them numerically, so the n-th is the one holding n - 1.

Complexity

• Time — O(log n + log x)
• Space — O(1)

Pitfalls

• Using n instead of n - 1 overshoots by one element.
• Writing the spare bits into positions where x already has ones would not increase the count of distinct values.
• At LeetCode's real limits the answer needs 64 bits; this version caps n and x so it fits in int.

Reference solution

Python

def minEnd(n: int, x: int) -> int:
    result = x
    rest = n - 1
    bit = 0
    while rest > 0:
        if not ((x >> bit) & 1):
            if rest & 1:
                result |= 1 << bit
            rest >>= 1
        bit += 1
    return result

JavaScript

var minEnd = function(n, x) {
    var result = x;
    var rest = n - 1;
    var bit = 0;
    while (rest > 0) {
        if (((x >> bit) & 1) === 0) {
            if (rest & 1) result |= 1 << bit;
            rest >>= 1;
        }
        bit++;
    }
    return result;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More greedy problems

• Minimum Number of Work Sessions to Finish the Tasks Medium
• Remove All Ones With Row and Column Flips Medium
• Minimum Impossible OR Medium
• Maximum OR Medium
• Number of Wonderful Substrings Medium
• Bitwise ORs of Subarrays Medium