Number Complement Leetcode Solution


Difficulty Level Easy
Frequently asked in Apple
Bit Manipulation Bits Cloudera

Problem Statement

In this problem, we are given a decimal number. The goal is to find its complement.

Example

N = 15
0
N = 5
2

Number Complement Leetcode Solution

Approach (Flipping bit by bit)

We can flip every bit in the integer ‘N’ to get its complement. The important part is, we cannot flip all of its 32 bits. As that would result in its binary 1’s complement. We only need to flip starting from the LSB to the leftmost set bit in the number. We can achieve that by dividing the given number, N by 2, till it becomes zero. And at each iteration, we can flip the corresponding bit.

Implementation of Number Complement Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int todo = num , i = 0;
    while(todo > 0) {
        num ^= (1 << i);
        todo >>= 1;
        ++i;
    }
    return num;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java Program

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int todo = num , i = 0;
        while(todo > 0) {
            num ^= (1 << i);
            todo >>= 1;
            ++i;
        }
        return num;
    }
}
0

Complexity Analysis of Number Complement Leetcode Solution

Time Complexity

O(log2N), where N = given integer. We iterate as many times as the number of bits in the given number.

Space Complexity 

O(1), as we only use constant memory.

Approach (Optimized)

The optimized approach is to not use any branching in the code. That is, to solve the code without any loops, or any basically, any branching instruction. In this approach, we first find a binary mask that has all bits set, starting from the ‘0th’ bit to the leftmost set bit in the given number, and then XOR it with itself. This will give us the required complement.

In order to find the required binary mask for N, we bitwise OR the given number with N >> 1, N >> 2, N >> 4, … N >> 16, where N >> k = right shifting N by k places. By this method, we would set all the bits after the Most Significant Bit (leftmost bit) and produce the required mask.

Implementation of Number Complement Leetcode Solution

C++ Program

#include <bits/stdc++.h>

using namespace std;

int findComplement(int num) {
    int mask = num;
    mask |= mask >> 1;
    mask |= mask >> 2;
    mask |= mask >> 4;
    mask |= mask >> 8;
    mask |= mask >> 16;
    return num ^ mask;
}

int main() {
    int n = 15;
    cout << findComplement(n) << endl;
    return 0;
}

Java Program

class number_complement {
    public static void main(String args[]) {
        int n = 15;
        System.out.println(findComplement(n));
    }

    public static int findComplement(int num) {
        int mask = num;
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        return num ^ mask;
    }
}
0

Complexity Analysis of Number Complement Leetcode Solution

Time Complexity

O(1), as the bitwise binary operations are very fast and though the operations take O(log2N), time complexity is constant for 32-bit integers.

Space Complexity 

O(1), as we only use constant memory space.