Number Complement — Editorial

Opening the reading…

Intuitionwhy the mask must match the binary length

The complement flips every bit that appears in num's binary representation, but it does not flip leading zeros. For example, 5 is written as 101, so its complement is 010, which is 2. The answer therefore needs one decision for each significant bit, not for every bit in the integer type.

A mask made of ones over exactly the same width solves this directly. XOR keeps a bit when the mask has 0 and flips it when the mask has 1, so XORing num with a same-width all-ones mask flips every relevant bit and nothing else. You can construct that mask by starting at 1 and repeatedly appending another 1 until it reaches num's highest set bit.

Approach

Start mask at 1, because every valid num has at least one significant bit and the one-bit number 1 already needs the mask 1.

While mask is smaller than num, shift mask left and set its new lowest bit to 1. This appends a one to the mask, so the loop stops at the all-ones value with the same bit length as num.

XOR the completed mask with num. Every one in the mask flips the corresponding bit, while no leading zero outside the mask can affect the result.

Return mask ^ num directly, because the XOR result already contains the complement in the required integer form and needs no conversion through a string or array.

Complexitythe cost is the number of significant bits

MEASURE	BOUND	WHY
Time	O(b)	Each loop iteration adds one bit to mask, and mask grows from one bit to b bits. No bit is revisited after it has been added, so the loop performs exactly b - 1 iterations in the nontrivial case.
Space	O(1)	Only the integer mask is extra working storage; the output is a single integer and is not counted as extra space. The bound stays constant even for the largest allowed num, although the loop takes its worst-case number of iterations when num has 31 bits.

Here b is the number of bits in num's binary representation, so b is at most 31 under the given constraint.

Annotated solutionC++ · iterative mask construction · complete judge-ready solution

CPPConstruct an all-ones mask with the same bit length as num, then XOR it with num.

#include <cstdint>

using namespace std;

class Solution {
public:
    int findComplement(int num) {
        int mask = 1;
        while (mask < num) {
            mask = (mask << 1) | 1;
        }
        return mask ^ num;
    }
};

The update mask = (mask << 1) | 1 performs two operations in the required order. The left shift makes room for one new bit, and the OR sets that new bit to one. The condition mask < num is also important: for num = 5, the mask sequence is 1, 3, 7, and 7 is the first value wide enough to cover 101. XORing 7 and 5 gives 2.