Python 0476.py
class Solution:
def findComplement(self, num: int) -> int:
mask = 1
while mask < num:
mask <<= 1
mask += 1
return mask ^ num
Difficulty
and has an acceptance rate of about 71% (700k+ submissions).
Typical patterns to solve this problem:
- Bit Manipulation
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a Solution class with a single method findComplement. The method receives a non-negative integer num and returns the integer that results from flipping every bit of num within the width of its most significant set bit. In other words, it computes the bitwise complement of num restricted to the minimal number of bits required to represent num in binary.
Key Steps
Initialization of the mask
The algorithm begins by creating a variable mask and setting it to the value 1. This variable will be transformed into a bit pattern consisting of all 1s that spans exactly the same width as the binary representation of num.
mask = 1
Expanding the mask to cover the full bit width
A while loop iteratively expands mask until it is at least as large as num. Inside the loop two operations are performed:
mask <<= 1shifts the current mask left by one position, effectively multiplying it by two and creating a new most-significant zero bit.mask += 1sets that newly created least-significant bit to1, turning the mask into a sequence of consecutive1s.
The loop condition mask < num guarantees that the process stops as soon as the mask reaches or exceeds num. When the loop terminates, mask holds a value that is one less than the next power of two greater than num, i.e., a binary number composed entirely of 1s whose length matches the length of num.
while mask < num:
mask <<= 1
mask += 1
Computing the complement with XOR
After the mask has been prepared, the final step applies the XOR operator between mask and num. Because mask contains 1s in every position that should be considered, XOR flips each bit of num within that range while leaving higher bits (if any) untouched. The result of this operation is the desired complement.
return mask ^ num
Edge Cases Handled
The loop condition mask < num naturally accommodates several edge situations:
-
Zero input: When
numis0, the loop body is never executed because the initialmaskvalue1is already greater thannum. The mask remains1, and the XOR operation yields1, which is the correct complement for a single-bit representation of zero. -
Power-of-two inputs: For values such as
1,2,4,8, etc., the mask expands until it becomes exactly one less than the next power of two. For example, withnum = 8(binary1000), the loop produces a mask of15(binary1111). XOR then flips the lower four bits, delivering7(binary0111), the expected complement. -
Maximum integer size: The loop increments the mask by shifting and adding
1until it surpassesnum. Because each iteration roughly doubles the mask, the number of iterations grows logarithmically with the magnitude ofnum. This behavior ensures that even very large integers are processed without overflow or excessive iteration counts.
Performance Optimizations
The algorithm leverages bitwise operations that are executed directly by the processor, resulting in minimal overhead. The mask construction uses a left shift (<<=) followed by an addition of 1, which together generate a contiguous series of 1s in a single pass without needing to count bits or allocate auxiliary structures. This approach avoids the need for converting the integer to a string or list representation, thereby keeping the execution fast and memory-light.
The final XOR operation is a constant-time bitwise operation that simultaneously flips all relevant bits, eliminating the need for per-bit iteration. By combining the mask generation and the XOR step, the method achieves an efficient solution that scales well with the size of the input integer.
ELI5 - Simplified Explanation
Imagine the computer sees numbers as a long string of light switches that are either on or off. This code is like a game where the computer takes a number you give it and flips every single switch. If a switch is off, it turns on. If a switch is on, it turns off.
First, the code creates a special tool called a mask. It starts small and grows until it is just as wide as the number you gave it. Once the tool is big enough, the computer uses it to swap the switches. It is like looking at a picture through a magic lens that turns all the dark spots into bright spots and all the bright spots into dark ones. After it finishes flipping all those little switches, the new arrangement of them makes a brand new number.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | |||||||
| WalkCCC | C++ | Java | ||||||||||
| leetcode.ca | C++ | Python | Java | JS | Go | TS | ||||||
| LeetcodeHelp | C++ | Python | Java | |||||||||
| Progiez | C++ | Python | Java | |||||||||
| github | BigEggStudy | C# | ||||||||||
| black-shadows | C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JS | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| halfrost | Go | |||||||||||
| JoshCrozier | JS | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| ruoru | Rust | |||||||||||
| Shamik07 | Dart | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| withaarzoo | C++ | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ | |||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||||||
| WalkCCC | C++, Java | |||||||||||
| leetcode.ca | C++, Go, Java, JavaScript, Python, TypeScript | |||||||||||
| LeetcodeHelp | C++, Java, Python | |||||||||||
| Progiez | C++, Java, Python | |||||||||||
| BigEggStudy | C# | |||||||||||
| black-shadows | C++, C++ | |||||||||||
| chandansgowda | Python | |||||||||||
| charles-wangkai | Java | |||||||||||
| DimitrisJim | C | |||||||||||
| everthis | JavaScript | |||||||||||
| fartem | Ruby | |||||||||||
| fpdjsns | C++ | |||||||||||
| halfrost | Go | |||||||||||
| JoshCrozier | JavaScript | |||||||||||
| keineahnung2345 | C++ | |||||||||||
| Krazune | C | |||||||||||
| linouk23 | C++ | |||||||||||
| lkwq007 | Python | |||||||||||
| ruoru | Rust | |||||||||||
| Shamik07 | Dart | |||||||||||
| sonugiri1043 | C++ | |||||||||||
| suxrobGM | C# | |||||||||||
| trung-hn | Python | |||||||||||
| varunu28 | Java | |||||||||||
| vli02 | C | |||||||||||
| vthwang | Java | |||||||||||
| withaarzoo | C++ | |||||||||||
| YuriSpiridonov | Python | |||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 1009: Complement of Base 10 Integer
Solved On The Same Day
- problem 496: Next Greater Element I
- problem 6: Zigzag Conversion
- problem 38: Count and Say
- problem 147: Insertion Sort List
- problem 148: Sort List
- problem 494: Target Sum
- problem 498: Diagonal Traverse
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality