Number Complement - Practice Coding Problems

Number Complement - Problem

Bit Manipulation Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: num = 5

› Output: 2

💡 Note: 5 in binary is 101. Flipping each bit: 1→0, 0→1, 1→0 gives us 010, which is 2 in decimal.

Example 2 — Single Bit

$ Input: num = 1

› Output: 0

💡 Note: 1 in binary is 1. Flipping the bit: 1→0 gives us 0.

Example 3 — Larger Number

$ Input: num = 7

› Output: 0

💡 Note: 7 in binary is 111. Flipping each bit: 1→0, 1→0, 1→0 gives us 000, which is 0 in decimal.

Constraints

1 ≤ num ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input Number

Given number 5 with binary representation 101

Flip All Bits

Change each 1 to 0 and each 0 to 1

Output Complement

Result is 010 in binary, which equals 2 in decimal

Key Takeaway

🎯 Key Insight: XOR with a mask of all 1's efficiently flips every bit in the number

Asked in

G Google 15 a Amazon 12 M Microsoft 8 Apple 6

The key insight is to use bit manipulation with XOR operation. Create a mask of all 1's matching the number's bit length, then XOR with the original number to flip all bits efficiently. Best approach is XOR with Mask. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ XOR with Mask	O(log n)	O(1)	Create a mask of all 1's and XOR with the original number
String Manipulation	O(log n)	O(log n)	Convert to binary string, flip each bit, convert back to integer

XOR with Mask — Algorithm Steps

Step 1: Find the position of the most significant bit
Step 2: Create a mask with all 1's up to that position
Step 3: XOR the original number with the mask

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Bit Length

Count bits in 5 (101₂) = 3 bits

Create Mask

Generate mask 111₂ (7₁₀) with 3 ones

XOR Operation

5 XOR 7 = 101₂ XOR 111₂ = 010₂ = 2

Code -

solution.c — C

#include <stdio.h>

int solution(int num) {
    // Find the position of the most significant bit
    int temp = num;
    int bitCount = 0;
    while (temp > 0) {
        temp >>= 1;
        bitCount++;
    }
    
    // Create mask with all 1's for bitCount positions
    int mask = (1 << bitCount) - 1;
    
    // XOR with mask to flip all bits
    return num ^ mask;
}

int main() {
    int num;
    scanf("%d", &num);
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Finding the highest bit position takes O(log n) time

⚡ Linearithmic

Space Complexity

O(1)

Only uses a few integer variables for calculations

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

987 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

XOR with Mask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler