Minimum Array End

Medium
742.

Minimum Array End

Minimum Array End is a medium coding problem on greedy and bit manipulation, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} x
 * @return {number}
 */
var minEnd = function(n, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Array End — Solution in Python, Java & C++

Minimum Array End solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Array End is a medium coding problem on greedy and bit manipulation, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Medium
  • Topics: Greedy, Bit Manipulation
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Minimum Array End

  1. Hint 1

    Every element must contain all of x's set bits, so the elements are x with extra bits added in the positions where x is zero.

  2. Hint 2

    Those free positions can be filled independently, which makes the n smallest valid values correspond to the numbers 0, 1, …, n - 1 written into the free slots.

  3. Hint 3

    So spread the binary digits of n - 1 into x's zero positions, from the low end upward.

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

Java

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

C++

int minEnd(int n, int x) {
    int result = x;
    int rest = n - 1;
    int bit = 0;
    while (rest > 0) {
        if (((x >> bit) & 1) == 0) {
            if (rest & 1) result |= 1 << bit;
            rest >>= 1;
        }
        bit++;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 264 greedy problems · the whole catalogue

Learn the technique: Greedy Algorithms · Bit Manipulation