✅ Easy Solution with Explanation | 🛑2 Approaches🛑 | Without Bit Manipulation | 🔥Beats 100%🔥
See the pattern?\n\n\nNumber   Binary     Complement  Complement Value\n1       =  1      ->    0     =     0\n\n2       =  10     ->    01    =     1\n3       
See the pattern?\n\n```\nNumber   Binary     Complement  Complement Value\n1       =  1      ->    0     =     0\n\n2       =  10     ->    01    =     1\n3       =  11     ->    00    =     0\n\n4       =  100    ->    011   =     3\n5       =  101    ->    010   =     2\n6       =  110    ->    001   =     1\n7       =  111    ->    000   =     0\n\n8       =  1000   ->    0111  =     7\n9       =  1001   ->    0110  =     6\n10      =  1010   ->    0101  =     5\n11      =  1011   ->    0100  =     4\n12      =  1100   ->    0011  =     3\n13      =  1101   ->    0010  =     2\n14      =  1110   ->    0001  =     1\n15      =  1111   ->    0000  =     0\n.\n.\n.\n```\nThe range of binary numbers for n bits is from 0 to ($$2^n - 1$$). For example, with 1 bit we can represent 1, with 2 bits we can represent 2 (10) and 3 (11), with 3 bits we can represent 4 (100), 5 (101), 6 (110), 7 (111), and so on. The complement of a binary number can be found by subtracting the number itself from the maximum value in its binary representation, which is ($$2^n - 1$$).\n\nTo represent 1 we need at least 1 bit so, n  = 1\n1 = ($$2^n -1$$) - number itself => 1 - 1 = 0 (Complement value)\n\nTo represent 2 and 3 we need at least 2 bits so, n  = 2\n2 = ($$2^n -1$$) - number itself => 3 - 2 = 1 (Complement value)\n3 = ($$2^n -1$$) - number itself => 3 - 3 = 0 (Complement value)\n.\n.\n.\nsimilarly, To represent 15 we need at least 4 bits so, n  = 4\n15 = ($$2^n -1$$) - number itself => 15 - 15 = 0 (Complement value)\n.\n.\n.\nand so on.\n\n\nThe max range value can be calculated with this `int tmp = (int) (Math.pow(2,digits(num))-1);`\n\nNow subtract the number from which we need to find the complement. `int res = tmp - num;` This will give us the complement of the number.\n\n\n# Approach 1: Using Binary Number Range, Without Bit Manipulation \n\n- Time complexity: O(log n)\n- Space complexity: O(1)\n\n```\nclass Solution {\n    public int findComplement(int num) {\n        int tmp = (int) (Math.pow(2,digits(num))-1);\n        return tmp - num;\n    }\n\n    static int digits(int n){\n        int count = 0;\n        while(n > 0){\n            n = n/2;\n            count++;\n        }\n        return count;\n    }\n}\n```\n\n\n# Approach 2: Optimizing Approach 1\n- Time complexity: O(1)\n- Space complexity: O(1)\n\n```\nclass Solution {\n    public int findComplement(int num) {\n        // Calculate the number of bits required to store the num\n        long digits = (long) (Math.log(num) / Math.log(2)) + 1;\n        \n        // Calculate (2 ^ digits) - 1\n        long tmp = (long) Math.pow(2, digits) - 1;\n        \n        // Subtract num from this value to get the complement\n        return (int) tmp - num;\n    }\n}\n```\n\n\n# Approach 3: Bit Manipulation\n\n- Time complexity: O(1)\n- Space complexity: O(1)\n\n```\nclass Solution {\n    public int findComplement(int num) {\n\t    return ~num & (Integer.highestOneBit(num) - 1);\n    }\n}\n```
['Bit Manipulation', 'Java']