What is the time complexity of Number Complement?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Number Complement?

This problem uses Bit Manipulation. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Number Complement?

Insight 1: The core idea is to create a 'mask' that has the same number of bits as the input number 'num', with all bits set to 1. Insight 2: By XORing the number 'num' with the 'mask', we effectively flip all the bits, thus computing the complement.

Which companies ask LeetCode 476. Number Complement in interviews?

This problem is frequently asked at Cloudera.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Number Complement - LeetCode 476 Solution

Number Complement - Complete Solution Guide

Number Complement is LeetCode problem 476, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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:

Detailed Explanation

The problem asks us to find the complement of a given integer. The complement is obtained by flipping all the bits (0s to 1s and 1s to 0s) in the binary representation of the number. For instance, the binary representation of 5 is '101', so its complement is '010', which is equal to 2 in decimal. The input is a positive integer 'num', and the output should be its complement.

Solution Approach

The solution involves first determining the number of bits required to represent the input number in binary. Then, we create a mask with the same number of bits, all set to 1. Finally, we perform a bitwise XOR operation between the original number and the mask. The result of the XOR operation is the complement of the original number.

Step-by-Step Algorithm

Step 1: Calculate the number of bits required to represent the number `num` in binary. In Python, we can use `num.bit_length()`. In Java, `Integer.highestOneBit(num)` gives the highest set bit, shifting it left by one and subtracting one creates the desired mask.
Step 2: Create a mask by left-shifting 1 by the number of bits calculated in Step 1, and then subtracting 1. This results in a number with all the bits set to 1 for the required length. (e.g., if `bits` is 3, the mask will be `(1 << 3) - 1 = 8 - 1 = 7`, which is `111` in binary).
Step 3: Perform a bitwise XOR operation (^) between the original number `num` and the `mask`. This flips all the bits in `num` that correspond to the bits set to 1 in the `mask`. The result of this XOR operation is the complement.
Step 4: Return the result of the XOR operation.

Key Insights

Insight 1: The core idea is to create a 'mask' that has the same number of bits as the input number 'num', with all bits set to 1.
Insight 2: By XORing the number 'num' with the 'mask', we effectively flip all the bits, thus computing the complement.
Insight 3: Determining the correct number of bits for the mask is crucial. Leading zeros in the original number are irrelevant for the complement calculation.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Bit Manipulation.

Companies

Asked at: Cloudera.

Number Complement | LeetCode 476

Easy

Bit Manipulation

Time: O(1)Space: O(1)

Solution Code

Available in:

class Solution {
    public int findComplement(int num) {
        int mask = (Integer.highestOneBit(num) << 1) - 1;
        return num ^ mask;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 476: Number Complement - Detailed explanation and solution approaches.

Topics

Bit Manipulation

Companies

Cloudera

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:476

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Calculate the number of bits required to represent the number `num` in binary. In Python, we can use `num.bit_length()`. In Java, `Integer.highestOneBit(num)` gives the highest set bit, shifting it left by one and subtracting one creates the desired mask.
2
Step 2: Create a mask by left-shifting 1 by the number of bits calculated in Step 1, and then subtracting 1. This results in a number with all the bits set to 1 for the required length. (e.g., if `bits` is 3, the mask will be `(1 << 3) - 1 = 8 - 1 = 7`, which is `111` in binary).
3
Step 3: Perform a bitwise XOR operation (^) between the original number `num` and the `mask`. This flips all the bits in `num` that correspond to the bits set to 1 in the `mask`. The result of this XOR operation is the complement.
4
Step 4: Return the result of the XOR operation.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The number of bit operations required to calculate the complement is independent of the size of the input number. Finding the bit length, creating the mask, and performing the XOR operation all take constant time. Therefore, both the time and space complexities are O(1).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Iterative Bit Flipping

Iterate through each bit of the number from right to left, flipping each bit and accumulating the result. This would involve using bitwise AND and OR operations.

Time: O(log n), where n is the input number.Space: O(1)

Trade-offs: This approach is less efficient than the main solution (O(log n) vs O(1)). The main solution is more concise and leverages bitwise operations for efficient calculation.

✨

Key Insights

1Insight 1: The core idea is to create a 'mask' that has the same number of bits as the input number 'num', with all bits set to 1.
2Insight 2: By XORing the number 'num' with the 'mask', we effectively flip all the bits, thus computing the complement.
3Insight 3: Determining the correct number of bits for the mask is crucial. Leading zeros in the original number are irrelevant for the complement calculation.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: `num = 1`. The bit length is 1, the mask is `(1 << 1) - 1 = 1`, and the complement is `1 ^ 1 = 0`. The solution correctly handles this case.
Edge case 2: Large numbers close to 2^31. The bit length calculation and mask creation should work correctly even with large numbers within the constraint range (1 <= num < 2^31).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly calculating the number of bits required for the mask. If the mask has too few bits, the complement will be incorrect. If it has too many, leading bits might be flipped.

✗Common mistake 2: Forgetting to subtract 1 when creating the mask. If you simply left shift 1 by the bit length, you get a number with a single bit set. Subtracting 1 sets all the bits below to 1.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Error detection and correction codes. Complements are used in parity checks and checksum calculations to detect errors during data transmission.

🏦Real-world scenario 2: Image processing. Bitwise operations, including complement operations, are used for image manipulation, such as inverting colors or creating negative images.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

XOR is your friend for "find the single number" problems. Remember: n & (n-1) clears the lowest set bit.

🎯 Interview Tip

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 25, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

❓

Frequently Asked Questions

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Number Complement"?

For this easy-level Bit Manipulation problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?