Construct the minimum bitwise array ii

Array Bit Manipulation

66.5% acceptance

Feb 23, 2026

354

You are given an array nums consisting of n prime integers. You need to construct an array ans of length n, such that, for each index i, the bitwise OR of ans[i] and ans[i] + 1 is equal to nums[i], i.e. ans[i] OR (ans[i] + 1) == nums[i]. Additionally, you must minimize each value of ans[i] in the resulting array. If it is not possible to find such a value for ans[i] that satisfies the condition, then set ans[i] = -1.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {
    fn solve(p: i32) -> i32 {
      if p == 2 { return -1; }
      // Find highest k such that bits 0..k of p are all 1
      let mut best = -1i32;
      for k in 0..31i64 {
        let mask = (1i64 << (k + 1)) - 1;
        if (p as i64) & mask == mask {
          let x = ((p as i64) & !mask) | ((1i64 << k) - 1);
          if best == -1 || (x as i32) < best {
            best = x as i32;
          }
        }
      }
      best
    }
    nums.iter().map(|&p| solve(p)).collect()
  }
}