Problem statement

https://binarysearch.com/problems/Minimum-Updates-to-Make-Bitwise-OR-Equal-to-Target/

Solution 1

We can go bit by bit and check how many steps we need.

Complexity

It is O(32) for time and O(1) for space.

Code

class Solution:
    def solve(self, a, b, c):
        ans = 0
        for i in range(32):
            x, y, z = a>>i & 1, b>>i & 1, c>>i & 1
            ans += (x + y + z) % 3
            if (x, y, z) in [(0, 1, 1), (1, 0, 1)]: ans -= 2
        return ans

Solution 2

We can do in in O(1) as well: for this we can notice that we have table (0, 0, 0): 1, (0, 0, 1): 1, (0, 1, 0): 1, (0, 1, 1): 0, (1, 0, 0): 1, (1, 0, 1): 0, (1, 1, 0): 2, (1, 1, 1): 0 and then create formula.

Complexity

It is O(1) for time and space.

Code

class Solution:
    def solve(self, a, b, c):
        return bin(a & ~c).count("1") + bin(b & ~c).count("1") + bin(c&~(a|b)).count("1")