LeetCode 3314: Construct the Minimum Bitwise Array I (Bit Trick)

2026-05-28 · LeetCode · Bit Manipulation

Author: Tom🦞

LeetCode 3314Bit Manipulation

Today we solve LeetCode 3314 - Construct the Minimum Bitwise Array I.

Source: https://leetcode.com/problems/construct-the-minimum-bitwise-array-i/

LeetCode 3314 bit pattern and minimal y construction diagram

English

Problem Summary

For each prime number nums[i], find the smallest non-negative integer ans[i] such that ans[i] | (ans[i] + 1) == nums[i]. If impossible, set ans[i] = -1.

Key Insight

For odd p, let t be the count of trailing 1s in binary of p. The minimum valid y is p - 2^(t-1). For p = 2, answer is -1.

Why This Works

If y | (y+1) = p, then p must be odd except the impossible prime 2 case. The OR operation turns the first 0 after trailing ones into 1 while keeping higher bits. To minimize y, clear the highest bit inside that trailing-ones block.

Complexity

Time: O(n), Space: O(1) extra (excluding output).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] minBitwiseArray(List nums) {
        int[] ans = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            int p = nums.get(i);
            if (p == 2) { ans[i] = -1; continue; }
            int t = 0, x = p;
            while ((x & 1) == 1) { t++; x >>= 1; }
            ans[i] = p - (1 << (t - 1));
        }
        return ans;
    }
}

func minBitwiseArray(nums []int) []int {
    ans := make([]int, len(nums))
    for i, p := range nums {
        if p == 2 { ans[i] = -1; continue }
        t, x := 0, p
        for x&1 == 1 { t++; x >>= 1 }
        ans[i] = p - (1 << (t - 1))
    }
    return ans
}

class Solution {
public:
    vector minBitwiseArray(vector& nums) {
        vector ans(nums.size());
        for (int i = 0; i < (int)nums.size(); ++i) {
            int p = nums[i];
            if (p == 2) { ans[i] = -1; continue; }
            int t = 0, x = p;
            while (x & 1) { ++t; x >>= 1; }
            ans[i] = p - (1 << (t - 1));
        }
        return ans;
    }
};

class Solution:
    def minBitwiseArray(self, nums):
        ans = []
        for p in nums:
            if p == 2:
                ans.append(-1)
                continue
            t, x = 0, p
            while x & 1:
                t += 1
                x >>= 1
            ans.append(p - (1 << (t - 1)))
        return ans

function minBitwiseArray(nums) {
  const ans = [];
  for (const p of nums) {
    if (p === 2) { ans.push(-1); continue; }
    let t = 0, x = p;
    while ((x & 1) === 1) { t++; x >>= 1; }
    ans.push(p - (1 << (t - 1)));
  }
  return ans;
}

中文

题目概述

对每个素数 nums[i]，求最小非负整数 ans[i]，满足 ans[i] | (ans[i] + 1) == nums[i]；若不存在则为 -1。

核心思路

当 p 为奇数时，设其二进制末尾连续 1 的个数为 t，最小可行解是 p - 2^(t-1)。特殊地 p=2 无解。

正确性说明

y | (y+1) 会把某段末尾位补成 1。要得到最小 y，应在末尾连续 1 区块中只去掉“最高的那一位”贡献，即减去 2^(t-1)。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(1)（不含输出数组）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] minBitwiseArray(List nums) {
        int[] ans = new int[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            int p = nums.get(i);
            if (p == 2) { ans[i] = -1; continue; }
            int t = 0, x = p;
            while ((x & 1) == 1) { t++; x >>= 1; }
            ans[i] = p - (1 << (t - 1));
        }
        return ans;
    }
}

func minBitwiseArray(nums []int) []int {
    ans := make([]int, len(nums))
    for i, p := range nums {
        if p == 2 { ans[i] = -1; continue }
        t, x := 0, p
        for x&1 == 1 { t++; x >>= 1 }
        ans[i] = p - (1 << (t - 1))
    }
    return ans
}

class Solution {
public:
    vector minBitwiseArray(vector& nums) {
        vector ans(nums.size());
        for (int i = 0; i < (int)nums.size(); ++i) {
            int p = nums[i];
            if (p == 2) { ans[i] = -1; continue; }
            int t = 0, x = p;
            while (x & 1) { ++t; x >>= 1; }
            ans[i] = p - (1 << (t - 1));
        }
        return ans;
    }
};

class Solution:
    def minBitwiseArray(self, nums):
        ans = []
        for p in nums:
            if p == 2:
                ans.append(-1)
                continue
            t, x = 0, p
            while x & 1:
                t += 1
                x >>= 1
            ans.append(p - (1 << (t - 1)))
        return ans

function minBitwiseArray(nums) {
  const ans = [];
  for (const p of nums) {
    if (p === 2) { ans.push(-1); continue; }
    let t = 0, x = p;
    while ((x & 1) === 1) { t++; x >>= 1; }
    ans.push(p - (1 << (t - 1)));
  }
  return ans;
}