# Minimum Array End
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-array-end)
Canonical: https://scaleengineer.com/dsa/problems/minimum-array-end
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
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`

# Approaches
## Iterative Search
This approach directly simulates the process of finding the `n`-th valid number. It starts with `x`, which is the first valid number, and then iteratively searches for the next strictly larger valid numbers one by one. A number `y` is considered "valid" if all bits set in `x` are also set in `y`, which is equivalent to the condition `(y & x) == x`. The simulation continues until the `n`-th valid number is found.
**Time:** O(Y_n - x) where Y_n is the final answer. The gap between consecutive valid numbers can be very large. For instance, if `x = 2^k - 1`, the next valid number is `x + 2^k`. With `n` up to `10^8`, the total number of increments can be huge, making this approach too slow. · **Space:** O(1) - The algorithm uses a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.; Directly models the problem statement without complex logic.
**Cons:** Extremely inefficient and will result in a Time Limit Exceeded (TLE) error for the given constraints.; The runtime depends on the magnitude of the final answer, not just the input size `n`.
### Explanation
The algorithm begins by recognizing that `x` is the smallest positive integer whose bitwise AND with itself is `x`. Thus, `x` is the first element in our sequence of valid numbers. To find the `n`-th element, we need to find `n-1` more valid numbers, each strictly greater than the previous one.

We can implement this by starting with a variable `current_num` set to `x`. We then enter a loop that runs `n-1` times. In each iteration, we search for the next valid number. We do this by incrementing `current_num` and then checking if it satisfies the condition `(current_num & x) == x`. If it doesn't, we continue incrementing `current_num` until the condition is met. This process guarantees that we find the smallest valid number that is greater than the previously found one. After `n-1` iterations, `current_num` will hold the `n`-th valid number, which is the minimum possible value for the last element of the array.

```java
class Solution {
    public long minArrayEnd(int n, int x) {
        long current_num = x;
        // We need to find n-1 more valid numbers after the first one (x).
        for (int i = 1; i < n; i++) {
            current_num++;
            // Keep incrementing until we find the next number y such that (y & x) == x.
            while ((current_num & x) != x) {
                current_num++;
            }
        }
        return current_num;
    }
}
```
### Algorithm
- Initialize a variable `current_num` to `x`. This represents the first and smallest valid number.
- Loop `n-1` times to find the subsequent `n-1` valid numbers.
- In each iteration, increment `current_num` to find the next potential candidate.
- Start an inner loop that continues as long as `current_num` is not a valid number. A number `y` is valid if `(y & x) == x`.
- Inside the inner loop, keep incrementing `current_num` until the validity condition is met.
- After the outer loop completes, `current_num` will hold the value of the `n`-th valid number.
- Return `current_num`.

## Bit Manipulation with Free Bits Mapping
This highly efficient approach leverages bitwise operations to construct the answer directly. It's based on the observation that any number `y` satisfying `y & x = x` must have all of `x`'s set bits also set. This means `y` can be formed by taking `x` and setting some additional bits that are `0` in `x` (let's call these "free bits"). The problem then transforms into finding the `n`-th smallest number that can be formed this way. This corresponds to finding the `(n-1)`-th number that can be formed using only the free bits, and adding it to `x`.
**Time:** O(log n + log x) - The main loop runs `O(log n)` times (for each bit in `n-1`). Inside the loop, we search for the next free bit. The bit position counter `bit_pos` only increases. Its final value is bounded by the number of bits in `n-1` plus the number of bits in `x`, which is `O(log n + log x)`. This is very fast. · **Space:** O(1) - The algorithm uses only a few variables, requiring constant extra space.
**Pros:** Extremely efficient and optimal for the given constraints.; Calculates the result directly without iteration over non-valid numbers.; Constant time complexity with respect to the magnitude of `n` and `x`, depending only on their number of bits.
**Cons:** The logic is less intuitive compared to a direct simulation.; Requires a good understanding of bitwise operations.
### Explanation
A number `y` is valid if and only if `y & x = x`. This implies that for every bit set in `x`, the corresponding bit must also be set in `y`. The other bits of `y` (where `x` has `0`s) can be either `0` or `1`. This means any valid number `y` can be expressed as `y = x | k`, where `k` is a number whose set bits are only at positions where `x` has `0`s (i.e., `k & x = 0`).

To find the `n`-th smallest valid number, we need to find the `n`-th smallest non-negative `k` satisfying `k & x = 0` and add it to `x`. The sequence of such `k` values in increasing order corresponds to taking the integers `0, 1, 2, 3, ...` and mapping their bits to the free bit positions of `x`.

Specifically, the `n`-th smallest valid number is constructed using the bits of `n-1`. Let `m = n-1`. We iterate through the bits of `m`. If the `i`-th bit of `m` is `1`, we find the `i`-th free bit position in `x` (0-indexed) and set that bit. The final result is `x` plus all these added bits.

```java
class Solution {
    public long minArrayEnd(int n, int x) {
        // We need to find the n-th number in the sequence of valid numbers.
        // A valid number 'y' must satisfy (y & x) == x.
        // This means y can be written as x | k, where (k & x) == 0.
        // The n-th smallest valid number corresponds to the n-th smallest k.
        // The n-th smallest k (for n>=1) is constructed from the bits of (n-1).
        long m = n - 1;
        long result = (long)x; // Start with x, and add bits to it.
        int bit_pos = 0;
        
        while (m > 0) {
            // Find the next bit position that is NOT set in x.
            // This is a "free" bit we can use.
            while (((x >> bit_pos) & 1) == 1) {
                bit_pos++;
            }
            
            // If the current LSB of m is 1, we set the corresponding free bit in our result.
            if ((m & 1) == 1) {
                result |= (1L << bit_pos);
            }
            
            // Move to the next bit of m and the next bit position for the next free slot.
            m >>= 1;
            bit_pos++;
        }
        
        return result;
    }
}
```
### Algorithm
- The core insight is that any valid number `y` must be of the form `x | k` where `k & x = 0`. This is equivalent to `y = x + k`.
- To find the `n`-th smallest valid number, we need to find the `n`-th smallest non-negative integer `k` such that `k & x = 0`.
- The `n`-th such `k` (for `n >= 1`) can be constructed by using the bits of the number `m = n - 1`.
- The bits of `m` are mapped to the "free" bit positions of `x` (positions where `x` has a `0` bit).
- Let `m = n - 1`. Initialize `result = x`.
- Iterate while `m > 0`:
  - Find the next available free bit position, `bit_pos`, where the bit of `x` is `0`.
  - If the least significant bit of `m` is `1`, set the `bit_pos`-th bit in the `result`.
  - Right-shift `m` to process its next bit and increment `bit_pos` to find the next free slot.
- Return the final `result`.

# Solutions
### Java

```java
class Solution {
public
  long minEnd(int n, int x) {
    --n;
    long ans = x;
    for (int i = 0; i < 31; ++i) {
      if ((x >> i & 1) == 0) {
        ans |= (n & 1) << i;
        n >>= 1;
      }
    }
    ans |= (long)n << 31;
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minEnd(self, n: int, x: int) -> int: n -= 1 ans = x for i in range(31): if x >> i & 1 ^ 1: ans |= (n & 1) << i n >>= 1 ans |= n << 31 return ans

```

### CPP

```cpp
class Solution {
public:
  long long minEnd(int n, int x) {
    --n;
    long long ans = x;
    for (int i = 0; i < 31; ++i) {
      if (x >> i & 1 ^ 1) {
        ans |= (n & 1) << i;
        n >>= 1;
      }
    }
    ans |= (1LL * n) << 31;
    return ans;
  }
};

```