#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/missing-number

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/bit-manipulation/missing-number

Repovive

Missing Number - Bit Manipulation | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Missing Number

Find the missing element using XOR.

Problem: Array contains $n$ distinct numbers from $0$ to $n$ . One is missing. Find it.

XOR approach: XOR all array elements with $0, 1, 2, ..., n$ . Pairs cancel, leaving the missing number.

function missingNumber(nums):
    n = nums.length
    result = n
    for i from 0 to n-1:
        result = result ^ i ^ nums[i]
    return result

Example: $[3, 0, 1]$ , $n = 3$ .

XOR: $3 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus 2 \oplus 3 = 2$ .
Missing: $2$ .

Alternative: Sum formula. Expected sum = $n(n+1)/2$ . Subtract actual sum.

Both are $O(n)$ time, $O(1)$ space (excluding input). XOR avoids potential overflow.