♾️ C++ | ✅100% Beats | ✅Full Explanation | 476. Number Complement
:) Please Upvote If You Like the Solution :)\n\n# Approach\n1. We know that we need to complement. For that we need to change 0 to 1 and 1 to 0.\n\n2. We need t
# :) Please Upvote If You Like the Solution :)\n\n# Approach\n1. We know that we need to complement. For that we need to change `0` to `1` and `1` to `0`.\n\n2. We need to think, what can we use here from our bitwise operators `(i.e &, |, ^, ~)`.\n\n3. Suppose we have,\n\n```\nEx. n = 10, binary-> 1010\n    1 0 1 0\n    x x x x\n  -----------\n    0 1 0 1\n\n```\n4. Think if we `xor` the `n` with `1111 (mask)`, we will get our desired answer. Like, \n\n```\n    1 0 1 0\n    1 1 1 1   ==> mask\n  ----------- ==> XOR\n    0 1 0 1\n```\n\n5. Now we just need to make `mask`, for that we can take `1` and do `(left shit + add one)` to make it `1111`. Like, \n\n```\nmask -> 0 0 0 1 \n        0 0 1 0 ==> left shift (mask << 1)\n        0 0 1 1 ==> add 1 (mask + 1)\n```\n\n6. we know that if we do `&` of `n` with `1111` then we will get that `n` itself.\n\n7. so we will do the `5th step` until `((mask & n) != n)`.\n\n8. At last we can able to make `1111 (mask)` and now return `(mask ^ n)`, see `4th step`. \n\n# Complexity\n- Time complexity: O(ceil(log(n)))\n- Space complexity: O(1)\n\n**Why Time complexity: O(ceil(log(n)))???**\n\n1. we are running the while loop for the number of bit of n. \n n = 2^x ==> (x = number of bits).\n Ex. n = 10, binary -> 1 0 1 0 (4 bits)\n    10 = 2^x\n    log2(10) = x\n    ceil (log2(10)) = x, \n\n2. log2(10) == 3.322, but we represent 10 in 4 bits so take ceil value.\n# Code\n```\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int mask = 1;\n        \n        while((mask & num) != num){\n            mask = mask << 1;\n            mask += 1;\n        }\n        return mask ^ num;\n    }\n};\n```
['Bit Manipulation', 'C', 'Bitmask', 'C++']