476. Number Complement
Problem Description
In this problem, we are given a positive integer num
. Our task is to return the complement of this number. The complement is defined as the number obtained by switching all bits of its binary representation: Every 0
bit becomes a 1
, and every 1
becomes a 0
.
For example, if the input is 5
, its binary form is 101
. Its complement will be 010
which, in decimal, is 2
. The challenge is to compute this complement without directly manipulating the binary string.
Intuition
The key to solving this problem lies in understanding bitwise operations. In particular, the XOR operation becomes very useful. XOR, or exclusive or, gives us a 1
bit whenever the bits in the same position of the two numbers are different, and a 0
bit when they are the same.
So, if we XOR the given number with a number that has all bits set to 1
, and is of the same length, we will effectively switch all bits of the original number - 0
s will become 1
s, and 1
s will become 0
s. This is exactly the complement.
To get a number with all bits set to 1
and of the same length as num
, we can use the fact that a power of two, when decreased by 1
, will give us a number with all bits set to 1
that is one less in size. For instance, 2^3
is 1000
in binary, and 2^3 - 1
is 0111
.
Therefore, we calculate 2
raised to the power of the length of the binary representation of num
minus 1
. To find the length of the binary representation, we convert num
to binary using bin(num)
, slice off the '0b' prefix with [2:]
, and then take the len
of it. Once we have this number, we can XOR it with num
to get the desired complement.
Solution Approach
The solution provided uses bitwise operators to obtain the complement of the given integer. There are no additional data structures used, and the entire procedure relies on built-in operations and an understanding of how numbers are represented in binary.
-
First, we convert the integer to its binary representation as a string using
bin(num)
.bin()
is a built-in Python function that takes an integer and returns its binary representation, prefixed with0b
. -
We then take the substring excluding the first two characters (
'0b'
) by using slice notation[2:]
. This gives us just the binary digits. -
We now look for the length of this binary string representation using
len()
. This length represents the number of bits in the original integer's binary representation. -
We raise
2
to the power of this length, which gives us a number that in binary has a1
followed by as many0
s as the length we found:2 ** len(bin(num)[2:])
. -
We then subtract
1
from this number. Because of the nature of binary numbers, subtracting1
from a power of2
gives us a sequence of1
s. For example,2 ** 3
is1000
in binary, and2 ** 3 - 1
is0111
. This sequence of1
s matches the length of our input numbernum
. -
Finally, we perform an XOR operation between the original number
num
and the number with the sequence of1
s to flip all the bits. In Python, the XOR operator is^
. -
The result of this operation
num ^ (2 ** (len(bin(num)[2:])) - 1)
is the complement of the input integernum
.
Here is a step-by-step conversion of 5
as an example:
bin(5)
is'0b101'
- Slicing off
'0b'
gives'101'
len('101')
is3
2 ** 3
is8
which is1000
in binary2 ** 3 - 1
is7
which is0111
in binary5 XOR 7
(or101 XOR 0111
) gives010
which is2
in decimal
No explicit loops or complex data structures are required, making this approach efficient and concise.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using the number 10
as a small example.
-
Convert the integer
10
to its binary representation. Using thebin()
function in Python, we havebin(10)
, which yields'0b1010'
. -
Remove the
'0b'
prefix by slicing.'0b1010'[2:]
becomes'1010'
. -
Find the length of the binary string
'1010'
:len('1010')
, which is4
. -
Compute
2
raised to the power of this length:2 ** len('1010')
is2 ** 4
, which gives us16
. In binary,16
is10000
. -
Subtract
1
from16
to get a number with4
bits set to1
:16 - 1
equals15
, and its binary form is'1111'
. -
Perform an XOR operation between the original number
10
(binary'1010'
) and15
(binary'1111'
):10 ^ 15
. In binary form, this operation looks like1010 XOR 1111
. -
The result of the XOR operation is
0101
in binary, which corresponds to5
in decimal.
The complement of 10
is therefore 5
. Using the aforementioned solution approach, the steps can be applied to any positive integer to find its binary complement without dealing with the binary string directly.
Solution Implementation
1class Solution:
2 def findComplement(self, num: int) -> int:
3 # Calculate the length of the binary representation of the number excluding the '0b' prefix.
4 binary_length = len(bin(num)) - 2
5
6 # Create a mask with all 1's that is the same length as the binary representation of the number.
7 mask = (2 ** binary_length) - 1
8
9 # XOR the number with the mask to flip all the bits and obtain its complement.
10 return num ^ mask
11
1public class Solution {
2 // This method computes the bitwise complement of a positive integer.
3 public int findComplement(int num) {
4 int complement = 0; // This will hold the result, the bitwise complement of 'num'.
5 boolean significantBitFound = false; // Flag to indicate when the first '1' bit from the left is found.
6
7 // Iterate from the 30th bit to the 0th bit (31st bit is not considered for a positive Integer).
8 for (int i = 30; i >= 0; i--) {
9 int bit = num & (1 << i); // Isolate the i-th bit of 'num'.
10
11 // Skip leading zeros - we don't want to consider them.
12 if (!significantBitFound && bit == 0) {
13 continue;
14 }
15
16 // Once the first non-zero bit is found, we flip the flag to true.
17 significantBitFound = true;
18
19 // If the current bit is 0, set the corresponding bit in the result.
20 if (bit == 0) {
21 complement |= (1 << i);
22 }
23 // No need to do anything if the bit is 1, as we want to flip it to 0 (which is the default).
24 }
25
26 return complement; // Return the computed complement.
27 }
28}
29
1class Solution {
2public:
3 int findComplement(int num) {
4 int complement = 0; // Initialize variable to store the complement
5 bool foundNonZeroBit = false; // Flag to check when the first non-zero bit is found
6
7 // Iterate from the 30th bit to the 0th bit (31st bit is not considered for a signed integer)
8 for (int i = 30; i >= 0; --i) {
9 int currentBit = (num & (1 << i)); // Check if the ith bit is set or not
10
11 // Skip leading zeroes and look for the first 1
12 if (!foundNonZeroBit && currentBit == 0) continue;
13
14 // After the first non-zero bit is found, set foundNonZeroBit to true
15 foundNonZeroBit = true;
16
17 // If the current bit is 0, set the corresponding bit in complement
18 if (currentBit == 0) {
19 complement |= (1 << i);
20 }
21 // If the current bit is 1, it remains 0 in the complement,
22 // so no action is needed since complement is initialized to 0
23 }
24 return complement; // Return the computed complement
25 }
26};
27
1function findComplement(num: number): number {
2 // Initialize a variable to store the complement of the number
3 let complement: number = 0;
4 // Boolean flag to check when the first non-zero bit is found
5 let foundNonZeroBit: boolean = false;
6
7 // Iterate from the 30th bit to the 0th bit (avoiding the 31st bit for a signed integer)
8 for (let i: number = 30; i >= 0; --i) {
9 // Isolate the ith bit of 'num' to determine if it is set (1) or not (0)
10 let currentBit: number = (num & (1 << i));
11
12 // Skip the leading zeroes until the first set bit is found
13 if (!foundNonZeroBit && currentBit === 0) {
14 continue;
15 }
16
17 // Once the first non-zero bit is found, set the flag to true
18 foundNonZeroBit = true;
19
20 // If the current bit is 0, set the corresponding bit in 'complement'
21 if (currentBit === 0) {
22 complement |= (1 << i);
23 }
24 // Note: When the current bit is 1, the complement bit will remain 0.
25 // This happens by default since 'complement' was initialized to 0.
26 }
27
28 // Return the computed complement of the original number
29 return complement;
30}
31
32// Usage example:
33let result = findComplement(5);
34console.log(result); // Outputs the complement of 5
35
Time and Space Complexity
Time Complexity
The time complexity of the function is O(1)
. This is because the operations within the function take constant time. The length of the binary representation of the number (len(bin(num)[2:])
) is proportional to the number of bits in num
, which is a fixed size for standard data types (like 32-bit or 64-bit integers). The exponentiation operation 2 ** <bit_length>
, bitwise XOR
operation, and subtraction are all completed in constant time regardless of the input size.
Space Complexity
The space complexity of the function is also O(1)
. No additional space that grows with the input size is used by the algorithm. Only a fixed number of variables are used regardless of the size of the input number, which means the amount of memory used does not scale with num
.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!