Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The small numeric bounds allow trying possible answers directly. Since candidates are checked in increasing order, the first value satisfying the bitwise equation is automatically the minimum. Each input value is independent of the others.

Approach

For each target value, initialize its answer to -1. Try candidates c from zero through target - 1 and test whether c OR (c + 1) equals the target. On the first match, store c and stop that search. Append the stored result to the output.

No candidate at or above the target is needed: for nonnegative integers, the OR is at least c + 1, which would then exceed the target. If the entire search fails, -1 correctly represents impossibility. In particular, the result of the OR is always odd, so the prime target two has no answer.

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        res = []

        for i in range(n):
            curr = -1
            for c in range(nums[i]):
                if c | (c + 1) == nums[i]:
                    curr = c
                    break
            res.append(curr)

        return res

Complexity analysis

Let M = max(nums). Time: O(n * M) in the worst case (equivalently O(sum(nums))). Auxiliary space: O(1) excluding the O(n) returned array.