476. Number Complement

1. Description

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

2. Example

Example 1

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

3. Constraints

• The given integer num is guaranteed to fit within the range of a 32-bit signed integer.
• num >= 1
• You could assume no leading zero bit in the integer’s binary representation.
• This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

4. Solutions

Bit Manipulation

Time complexity: O(1)
Space complexity: O(1)

class Solution
{
public:
    // int findComplement(int num)
    int findComplement(int num)
    {
        int result = 0, leftMove = 31;

        // find the first 1 bit
        while(leftMove >= 0 && (num & (1 << leftMove)) == 0) leftMove--;

        // then, find the first 0 bit
        while(leftMove >= 0 && (num & (1 << leftMove)) == 1) leftMove--;

        for( ; leftMove >= 0; leftMove--)
        {
            if((num & (1 << leftMove)) == 0)
                result += (1 << leftMove);
        }

        return result;
    }
};

Definition

Time complexity: O(1)
Space complexity: O(1)

class Solution
{
public:
    // int findComplement(int num)
    int findComplement(int num)
    {
        long sum = 1;
        while (num >= sum) sum <<= 1;

        return (sum - 1 - num);
    }
};