Clear and Intuitive Explanation of Bit Manipulation | Python
Intuition\nConsider the i\'th bit of c. There are two cases:\n\na) The i\'th bit is equal to 0\nThis means the i\'th bit in a and b must both be 0. We need to f
# Intuition\nConsider the i\'th bit of `c`. There are two cases:\n\na) The `i`\'th bit is equal to 0\nThis means the `i`\'th bit in `a` and `b` must both be 0. We need to flip any of the 1-bits to 0.\n\nb) The `i`\'th bit is equal to 1\nThis means either the `i`\'th bit in `a` or the `i`\'th bit in `b` must be 1. If neither are 1, we must flip at least one bit.\n\n# Approach\nIterate through each bit from 0 to 30 (as the problem states `a,b,c <= 10^9` and `10^9 < 2^30`) in numbers a, b and c. We then inspect the bit in c and consider each of the two cases listed above.\n\n# Complexity\n- Time complexity: O(1). Although we are iterating from 0 to 30, the number of iterations is constant (31 in this case), so the time complexity is O(1).\n\n- Space complexity: O(1)\n\n# Code\n```\nclass Solution:\n    def minFlips(self, a: int, b: int, c: int) -> int:\n        flips = 0\n        for i in range(31):\n            # i\'th bit of c is 1\n            if (c >> i) & 1:\n                flips += ((a >> i) & 1) == 0 and ((b >> i) & 1) == 0\n            # i\'th bit of c is 0\n            else:\n                flips += (a >> i) & 1\n                flips += (b >> i) & 1\n        return flips\n```\n\n# Get Faster Interview Prep Results with Top Algos\nWe all know how time-consuming it is to prepare for interviews and how frustratingly difficult it is to improve. We made **Top Algos** - a tool recommends the perfect algorithm problem based on your current skill level to help you improve the fastest in the shortest amount of time. Top Algos is your personalized coach that learns your skill level and finds the best problem you need to solve to improve.\n\nThe beta version of the product is available for **free** right now! You can sign up at https://topalgos.xyz/.
['Math', 'Bit Manipulation', 'Python', 'Python3']