Single Number


Given an array of integers where every element appears twice except for one, write a function to find that single number using Bit manipulation.

Function signature:
function findSingleNumber(array: number[]): number


Input: [3, 4, 5, 3, 4]
Output: 5


The problem requires us to find the single number in an array of integers where every other element appears twice. We can solve this problem efficiently using Bit manipulation. We will use the XOR operator to solve this problem.

The XOR operator returns 1 when the corresponding bits of two numbers are different, and 0 when they are the same. Since every number appears twice except for one, if we XOR all the numbers in the array, we will be left with the unique number.

We can use a loop to iterate through the array and perform the XOR operation on each number with the previous result. We initialize the result with the first element in the array.

Here's the step-by-step approach:

  • Initialize a variable
    to the first element in the array
  • Iterate through the array starting from the second element

  • For each element, perform the XOR operation with the
    variable and update
    with the result
  • After the loop, return the
    variable, which will be the unique number

Here's the code for the function:

function findSingleNumber(array) {
  let single = array[0];
  for (let i = 1; i < array.length; i++) {
    single = single ^ array[i];
  return single;

Big O Complexity Analysis: The time complexity of this solution is O(n) since we iterate through the array once. The space complexity is O(1) since we only use a constant amount of extra space to store the