Minimum array end

Bit Manipulation

55.5% acceptance

Feb 23, 2026

813

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

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_end(n: i32, x: i32) -> i64 {
    // Embed (n-1) into the free (0) bit positions of x
    let mut rem = (n as i64) - 1; // remaining bits to place
    let x = x as i64;
    let mut result = x;
    let mut bit = 1i64;

    while rem > 0 {
      // Find the next 0-bit position in result
      if result & bit == 0 {
        // This bit is free; place the LSB of rem here
        if rem & 1 == 1 {
          result |= bit;
        }
        rem >>= 1;
      }
      bit <<= 1;
    }
    result
  }
}