algorithm notes: leetcode#476 number complement

Problem

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

Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 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: 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.

Solution

Basic idea

Use XOR. Binary format of the number we need to XOR the given number is made up of 1 and it shares the length with the input number’s binary format. For example, binary format of 5 is ‘101’, then ‘101’ ^ ‘111’ = ‘10’, which is 2. Then, we need to figure out length of input number’s binary format, which can be completed by len(bin(num)). And, (1<<len(bin(num)))-1 can help to get the number used to XOR.

Python implementation

1
2
3
4
5
6
7

class :
    def findComplement(self, num):
        """
        :type num: int
        :rtype: int
        """
        return num^((1<<len(bin(num))-2)-1)

Java implementation

1
2
3
4
5

class  {
    public int findComplement(int num) {
        return num ^ ((1<<Integer.toString(num, 2).length()) - 1);
    }
}

Time complexity analysis

O(1).

Space complexity analysis

O(1).

Links

476. Number Complement
476. 数字的补数
(中文版) 算法笔记: 力扣#476 数字的补数