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 num, return its complement.
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.
Constraints:
- 1 <= num < 231
My Solution
We can solve this problem by examining each bit in num, flipping it and OR-ing the flipped value to our output. We get each bit in num by AND-ing it with 1. We then flip it. Finally we keep track of our current bit position in the output and OR the flipped value with the corresponding bit position. We then right shift num by 1 to move onto the next bit. We do this until num is 0, which means we have dealt with every bit.
Time complexity is O(1) because we are dealing with a constant 32 bits. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int findComplement(int num) {
int comp = 0;
int pos = 0;
while (num > 0) {
int bit = (num & 1);
if (bit == 0) {
bit = 1;
}
else {
bit = 0;
}
comp |= (bit << pos);
num >>= 1;
pos++;
}
return comp;
}
}