Leetcode 3314

3314. Construct the minimum bitwise Array 1

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

input是list of int。 output也是list of int。

要求是每个output element ans[i]和ans[i] + 1的bitwise OR的结果是input对应的nums[i].

并且需要保证ans[i]最小。

1. 试验

简单的试几个例子。给定的例子是[2, 3, 5, 7]。

2(10)没有ans[i] | ans[i] + 1。

3(11)可以是1(1) | 2(10) = 3(11)

5(101)可以是4(100) | 5(101) = 5(101)

7(111)可以是3(11)和4（100） = 7（111）

2. 思想

既然需要保证ans[i]最小，同时观察到ans[i]始终小于nums[i]。

那么我们可以从 j: 0 -> nums[i] - 1开始试，如果满足j | (j + 1) == nums[i]，那么我们就把j推到ans里，如果没有找到，推-1。

code

def minBitwiseArray(nums: list[int]) -> list[int]:
    ans = []
    for elem in nums: # iterate through each element in nums
        for j in range(elem): # iterate through 0 -> nums[i] - 1
            if j | (j + 1) == elem:
                ans.append(j)
                break # DON'T MISS THIS!!!
        else:
            ans.append(-1)
    return ans

The big O is O(nm). Where n is the length of nums, and m is the average value of all elements.

3. 优化方案。可不可以O(n)?

继续找几个规律：

1000 | 1001 = 1001

1011 | 1100 = 1111

101010 | 101011 = 101011

10001111 | 10010000 = 10111111

由此，我们可以得到一个基本的观察。ans[i] | (ans[] + 1) 实际上就是把从右到左第一个0翻转成了1.

那么，给定nums[i]，我们只需要找到从右到左的连续1中的最后一个1，把它变成0就可以了。

根据以上的几个例子验证一下：

1001 -> 1000

1111 -> 0111 (不是1011， 因为0111是最小的)

101011 -> 101001 (依然是最小的)

10111111 -> 10011111

具体的操作：

Given an element i in nums, If last bit is 0, append -1.

Find the rightmost 0. To do this, we can plus 1, and do a a & -a operation to find the rightmost 1.

Move right one bit, so we have the location of the last 1 in a row of 1s from right to left.

From i, deduct the above 0100..000 like binary.

code

def minBitwiseArray(nums: list[int]) -> list[int]:
    ans = []
    for i in nums:
        if i % 2 == 0
            ans.append(-1)
        else:
            ans.append(i - ((i + 1) & (-i - 1)) // 2)
    return ans