Problem Statement

Given a positive integer num, find its complement.

The complement of an integer is defined as flipping all the bits in its binary representation (0 → 1, 1 → 0).

Example:

Input: num = 5
Output: 2
Explanation: 
Binary of 5 = 101
Complement = 010 = 2

Input: num = 1
Output: 0
Explanation:
Binary of 1 = 1
Complement = 0

Constraints:

• 1 ≤ num < 2³¹

---

Approach to Solve the Problem (Simple Language)

1. Understand bit flipping:
   • Complement flips each bit.
   • Example: 5 in binary is 101, complement is 010.
2. Use a mask to flip bits:
   • Create a mask with all bits set to 1 for the length of num’s binary representation.
   • XOR the number with the mask to flip all bits.
3. Steps in short:
   • Find the number of bits in num.
   • Construct a mask of the same length with all 1s.
   • Return num ^ mask (XOR with mask flips the bits).

Why XOR works:

• 0 XOR 1 = 1
• 1 XOR 1 = 0

---

Java Code Solution

public class NumberComplement {

    public static int findComplement(int num) {
        // Step 1: Create a mask with all 1s of the same bit length as num
        int mask = 1;
        while (mask < num) {
            mask = (mask << 1) | 1; // Shift left and set next bit to 1
        }

        // Step 2: XOR num with mask to get complement
        return num ^ mask;
    }

    public static void main(String[] args) {
        int num = 5;
        int result = findComplement(num);
        System.out.println("Complement of " + num + " is: " + result); // Output: 2
    }
}

---

Dry Run Example

Input:

num = 5

Step-by-step Execution:

1. Binary of 5: 101 (3 bits)
2. Build mask:
   • mask = 1 → binary: 001
   • mask << 1 | 1 → 3 → binary: 011
   • mask << 1 | 1 → 7 → binary: 111 (mask >= num, stop)
3. XOR with mask:

   num   = 101 (5)
   mask  = 111 (7)
   XOR   = 010 (2)

4. Return 2.

---

Textual Diagram for Understanding

num = 5 -> binary 101
mask = 111 (same number of bits)
num ^ mask = 101 XOR 111 = 010 -> decimal 2

---

Complexity Analysis

• Time Complexity: O(log num)
  • We shift mask left until it exceeds num, which depends on the number of bits (~log2(num)).
• Space Complexity: O(1)
  • Only a few integer variables used.