Complement of Base 10 Integer - Practice Coding Problems

Complement of Base 10 Integer - 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 n, return its complement.

Input & Output

Example 1 — Basic Case

$ Input: n = 5

› Output: 2

💡 Note: 5 in binary is 101. Flipping all bits gives 010, which is 2 in decimal.

Example 2 — Single Bit

$ Input: n = 1

› Output: 0

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

Example 3 — Power of Two

$ Input: n = 4

› Output: 3

💡 Note: 4 in binary is 100. Flipping all bits gives 011, which is 3 in decimal.

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Integer n = 5 (binary: 101)

Process

Flip all bits: 0→1, 1→0

Output

Result = 2 (binary: 010)

Key Takeaway

🎯 Key Insight: XOR with a mask of all 1's flips every bit efficiently in O(1) time

Asked in

G Google 15 a Amazon 12 🍎 Apple 8 M Microsoft 10

The key insight is to use XOR with a mask of all 1's to flip bits efficiently. Create a mask with (1 << bit_length) - 1 then XOR with the original number. Best approach is bit manipulation with Time: O(1), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ One-Pass Bit Manipulation	O(1)	O(1)	Calculate mask and perform XOR in single optimized operation
Bit Manipulation with XOR Mask	O(log n)	O(1)	Find bit length, create mask, XOR to flip all significant bits
String Conversion Approach	O(log n)	O(log n)	Convert to binary string, flip each bit, convert back to integer

One-Pass Bit Manipulation — Algorithm Steps

Find highest set bit position
Generate mask using bit shifting
XOR original number with mask

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Analysis

n = 5, binary = 101

Direct Mask

Use bit_length() → mask = 111

XOR Result

101 ⊕ 111 = 010 = 2

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    // Handle edge case
    if (n == 0) {
        return 1;
    }
    
    // Create mask and return complement
    int mask = (1 << (32 - __builtin_clz(n))) - 1;
    return n ^ mask;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(1)

Uses built-in bit operations that are constant time

✓ Linear Growth

Space Complexity

O(1)

Only uses constant extra space for mask calculation

✓ Linear Space

85.0K Views

Medium Frequency

~15 min Avg. Time

2.8K 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

One-Pass Bit Manipulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler