Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Incrementing a number changes its trailing ones to zeros and the first following zero to one. OR with the original restores those trailing ones, so the target differs from the candidate by exactly one cleared bit within the target's trailing run of ones. Clearing the highest possible bit gives the smallest candidate.

Approach

For each target, scan bits upward from position zero while they are set. At every such position, form a candidate by clearing that bit with XOR, replacing the previous candidate. Higher cleared bits subtract larger powers of two, so the last candidate is the minimum. Stop at the first zero bit and overwrite the input value with the result.

If the least significant bit is zero, there is no candidate and the result stays -1. Clearing any bit in a trailing-one run works because the lower bits remain ones and incrementing carries exactly into the cleared position, reconstructing the target under OR.

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

        for i in range(n):
            res = -1
            pos = 0
            while (nums[i] & (1 << pos)) != 0:
                res = nums[i] ^ (1 << pos)
                pos += 1
            nums[i] = res

        return nums

Complexity analysis

Let M = max(nums). Time: O(n log M). Auxiliary space: O(1) because results overwrite the input array.