[C++] Simple Approaches (W/ Explanation) | Faster than 100%
Brute Force Approach :\n\n The Brute force approach to solve the problem would be to first convert the given number into its binary representation and then flip
**Brute Force Approach :**\n\n* The Brute force approach to solve the problem would be to first convert the given number into its binary representation and then flip every bit in the binary representation. \n* After changing all 0\u2019s and 1\u2019s convert the binary representation to number.\n\nTime Complexity :  O(n) - n = no. of bits in ```num```\n\nAuxiliary Space : O(n) \n\n**Code :**\n```\nclass Solution {\npublic:\n    int findComplement(int num) {\n\t\tvector<int> v;\n\t\twhile (n != 0) {    //convert the number to it\'s binary form & store the bits in "v"\n\t\t\tv.push_back(num%2);\n\t\t\tnum = num / 2;\n\t\t}\n\t\treverse(v.begin(), v.end());\n\t\tfor (int i = 0; i < v.size(); i++) v[i] = (v[i]==0) ? 1 : 0;    //Flip the bits in the binary form\n\t\t// convert back to number representation\n\t\tint two = 1;\n\t\tfor (int i = v.size() - 1; i >= 0; i--) {\n\t\t\tnum = num + v[i] * two;\n\t\t\ttwo = two * 2;\n\t\t}\n    return num;\n    }\n};\n```\n\n**XOR Approach :**\n* The only operation that can reverse the bits of a number (say : ```101``` to ```010``` is XOR (```^```) operation. \n* So we need to XOR the given number with a number that has the same no. of bits & all bits set to 1 (here, ```111```).\n* **How to count the number of bits in the given number ?**\n1. Initialize 2 variables ```ans = 1``` & ```n = num```.\n2. Until n is <= 1, do ```n >>= 1``` (decrementing 1 bit in ```n```), ```ans <<= 1``` (incerementing 1 bit in ```ans```) and ```ans |= 1``` (Setting the last bit of ```ans```).\n\n* Now that we have obtained a number that has as many bits as the input, perform **XOR** between the 2 numbers to flip all the bits of the input number.\n\nTime Complexity : O(logn) (Each time we\'re doing n = n/2) - Where n = ```num```\n\nSpace Complexity : O(1) - No extra space used\n\n**Code :**\n```\nclass Solution {\npublic:\n    int findComplement(int num) {\n        int n = num, ans = 1;\n        while(n != 1){\n            n >>= 1;\n            ans <<= 1;\n            ans |= 1;\n        }\n        \n        ans ^= num;\n        \n        return ans;\n    }\n};\n```\n\nIf you like my solutions & explanation; please upvote :)\n\n\n\n
['Bit Manipulation', 'C', 'C++']