1009-complement-of-base-10-integer

Try it on leetcode

Description

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer n, return its complement.

 

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

 

Constraints:

• 0 <= n < 109

 

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Solution(Python)

class Solution:
    # Question: given n flip al it's bits
    # For Example: for "101" return "010"
    #
    # Draft:
    # we needed  a bit manipulation technique that flips the
    # bits
    #       1.and - not useful here
    #       2.Or - not useful here
    #       3. >> / << - not useful here
    #
    #       4.xor - 1^0 = 1 1^1 = 0 (i.e xor with 1's flips the bits)
    #       5.~ = one' complement
    #
    # which gives us Xor and complement,
    # 1.xor:
    #       we can use a mask lets say 11111 with bit length same as n
    #        constructing the mask of length log(n) can be done in loop
    #       by formula mask = (2*mask+1) and then xoring with the n
    #
    # 2.complement:  works by invering each bit of the input
    #
    #
    # Time Complexity: O(log(n))
    # Space Complexity: O(1)
    def bitwiseComplement(self, n: int) -> int:
        mask = 1
        while mask < n:
            mask = 2 * mask + 1
        return mask ^ n