Leetcode 476 - Number Complement

Problem Statement

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

Note:

The given integer is guaranteed to fit within the range of a 32-bit signed integer.
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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def findComplement(self, num):
b = bin(num)[2:]
c = ""
for i in b:
if i == '1':
c += '0'
else:
c += '1'
return int(c, 2)

Time: O(N) where N is the number of bits in num

Space: O(N) where N is the number of bits in num

Explanation

In python, to operate on the bit-level there must be an O(log N) call to bin() which creates a binary string representation of num. Notice the usage of [2:] which strips out the leading ‘b’ character for binary string. After that, you’re just building up a binary string to represent each flipped bit and converting it to an integer by specifiying base 2.