✅ [C++/Python] Simple Solutions w/ Explanation | Brute-Force +Bit-Manipulation Tricks + In-Built
We are given an integer num and we need to return its complement\n\n---\n\n\u2714\uFE0F Solution - I (Brute-Force)\n\nWe can simply iterate and find the leftmos
We are given an integer `num` and we need to return its complement\n\n---\n\n\u2714\uFE0F ***Solution - I (Brute-Force)***\n\nWe can simply iterate and find the leftmost bit (MSB) that is set. From that point onwards, we flip every bit till we reach the rightmost bit (LSB). To flip a bit, we can use `^ 1` (XOR 1) operation. This will flip a bit to 0 if it is set and flip to 1 if it is unset.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int i = 31;\n        while((num & 1 << i) == 0) i--;   // skip the left 0 bits till we reach the 1st set bit from left\n        while(i >= 0)\n            num ^= 1 << i--;              // flip all bits by XORing with 1\n        return num;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def findComplement(self, num):\n        i = 31\n        while (num & 1 << i) == 0: \n            i -= 1\n        while i >= 0:\n            num ^= 1 << i\n            i -= 1\n        return num\n```\n\n***Time Complexity :*** <code>O(N)</code>, where `N` is the number of bits. In this case, since we are starting from `i=31`, it should be constant but I am denoting time complexity of this approach as generalized `O(N)`\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - II (Bit-Manipulation Tricks)***\n\nThe above method basically finds the leftmost set bit and XORs the remaining bits with 1. A more efficient way to do the same would be to simply XOR `num` with another number having all bits to the right of nums\'s 1st set bit as 1 and rest bit to left as 0. This would achieve the same thing as above.\n\n```py\nFor eg. num = 13\n=>  num  = 13  (1101)\n=>  mask = 15  (1111)\n--------------------\n   ^       2   (0010)    We got all the bits flipped\n```\n\n* **But how to get `mask`?** \n\t* A simple way would be  to initialize `mask = 0` and keep flipping bits of it to 1 starting from the rightmost bit (LSB) till we reach the leftmost set bit of `num`. \n\n* **Now, how do we know that we reached the leftmost set bit in `num`?**\n\t* We use another variable `tmp = num`. Each time, we will rightshift tmp essentially removing the rightmost bit. When we remove the leftmost set bit from it, it will become 0. Thus, we loop till `tmp` is not 0.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int mask = 0;                                 // all bits in mask are initially 0\n        for(int tmp = num; tmp; tmp >>= 1)            // set bits in mask to 1 till we reach leftmost set bit in num\n            mask = (mask << 1) | 1;                   // leftshifts and sets the rightmost bit to 1\n\t\t\t\n        return mask ^ num;                            // finally XORing with mask will flip all bits in num\n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def findComplement(self, num):\n        mask, tmp = 0, num\n        while tmp:\n            mask = (mask << 1) | 1\n            tmp >>= 1\n        return mask ^ num\n```\n\t\nAnother way to do the same would be to the other way around and start with mask with all bits as 1. Then we keep setting rightmost bits in `mask` to 0 one by one till there are no common set bits left in `num` and `mask` (`num & mask == 0` when no common set bits are present).\n\n```py\nFor eg. num = 13 (1101)  and  mask = -1 (111...1111)  [all 32 set bits are set in -1 binary representation]\n \n1. num =  000...1101 \n   mask = 111...1110   => we still have common set bits\n   \n2. num =  000...1101 \n   mask = 111...1100   => we still have common set bits   \n  \n3. num =  000...1101\n   mask = 111...1000   => we still have common set bits  \n   \n4. num =  000...1101 \n   mask = 111...0000   => no more common bits left\n```\n\n* **Now what?**\n\n\t* Now we can simply flip all bits in `mask` (using `~` operator). It will now have all rightmost bits set to one starting from leftmost set bit in `num`, i.e, we now have the same `mask` that we had in previous approach.\n\t* Now, we can XOR it with `num` and we get the flipped result\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int findComplement(int num) {\n        uint mask = -1;                             // -1 is represented in binary as all bits set to 1\n        while(mask & num) mask <<= 1;               // remove rightmost bits 1 by 1 till no common bits are left\n        return ~mask ^ num;                         // XORs with 1 & flips all bits in num starting from the leftmost set bit \n    }\n};\n```\n\n**Python**\n```python\nclass Solution:\n    def findComplement(self, num):\n        mask = -1\n        while mask & num: mask <<= 1\n        return ~mask ^ num\n```\n\nThis approach used 1 less operation inside loop (1st approach used 3 operations: right-shift `>>` on tmp, left-shift `<<` on mask and `|` with 1 to set rightmost bit. This one uses 2: `&` to check if there are common bits in `mask` and `num` and left-shift `<<` to remove the right set bits one by one)\n\n***Time Complexity :*** <code>O(P) / O(log num)</code>, where `P` is the position of leftmost set bit in `num`. <code>O(P) ~ O(log<sub>2</sub>(num))</code>\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - III (Flip Bits from Right to Left)***\n\nWe can start from the right-end and flip bits one by one. This is somewhat similar to 1st solution in above appraoch. But here we will not use mask but rather a bit starting with `i=1` and just directly XOR it with `num`, then left-shift it & repeat thus flipping the bits in `num` one by one. \n\nSo, how do we know when to stop? We stop as soon `i > num`. This denotes that we have passed the leftmost set bit in `num` and thus we have flipped all the bits that needed to be flipped.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int i = 1;\n        while(i <= num)\n            num ^= i,\n            i <<= 1;\n        return num;\n    }\n};\n```\n\n**Python**\n```python\nclass Solution():\n    def findComplement(self, num):\n        i = 1\n        while i <= num:\n            num ^= i\n            i <<= 1\n        return num    \n```\n\n***Time Complexity :*** <code>O(P) / O(log num)</code>\n***Space Complexity :*** `O(1)`\n\n---\n\n\u2714\uFE0F ***Solution - IV (Built-in Methods)***\n\nThere are built-in methods provided by languages such as `__builtin_clz` in C++ which counts leading zeros, `highestOneBit` in Java which returns the number with only its leftmost bit set and so on... These methods can be used to solve this problem as well using the same logic as above.\n\n**C++**\n```cpp\nclass Solution {\npublic:\n    int findComplement(int num) {\n        return ~(-1u << (32 - __builtin_clz(num))) ^ num;\n// or:  return ~(-1u << int(log2(num))+1) ^ num; \n    }\n};\n```\n\n**Python**\n```python\nclass Solution():\n    def findComplement(self, num):\n        return ~(-1 << int(log2(num))+1) ^ num\n```\n\n\n***Time Complexity :*** <code>O(1)</code>, `__builtin_clz` usually translates to single machine instruction and should be considered constant. The `log` complexity might be implementation dependent but should atleast be costlier by some factor than `__builtin_clz`\n***Space Complexity :*** `O(1)`\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]