#136 - Single Number

EasyBit Manipulation

Given a non-empty array of integers nums, every element appears twice except for one. Find the element that appears only once. You must use O(1) extra space.

Input	Output
nums = [2,2,1]	1
nums = [4,1,2,1,2]	4
nums = [1]	1

Solution Space

Try it

/**
 * Finds the element that appears exactly once (all others appear twice).
 * XOR of all elements cancels out the pairs, leaving the single number.
 *
 * @param nums Array where every element appears twice except one
 * @returns The single number
 */
export function singleNumber(nums: number[]): number {
  let result = 0;
  for (const num of nums) {
    result ^= num;
  }
  return result;
}

Approach: XOR – `a ^ a = 0` and `a ^ 0 = a`. XOR-ing all elements cancels every pair, leaving the unique element.

Time: O(n) – single pass.

Space: O(1) – one variable.

#1143 Longest Common Subsequence

#338 Counting Bits