Array Reduce Transformation - Leetcode Solution

Problem:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1] Output: 1

Solution:

In this problem, we have to find the single integer in an array where all other integers are repeated twice. We can use a hash table or set to keep track of the numbers that we have encountered so far but this will require extra space. However, we can solve this problem without using extra space by utilizing the XOR operation.

The XOR operation has the following properties:

1. XORing a number with itself results in 0.
2. XORing a number with 0 results in the number.

If we XOR all the elements in the array, the duplicate elements will cancel each other out and we will be left with the single integer.

Let's see an example:

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

We start by initializing a variable result to 0. We then XOR each element of the array with result. The first element in the array is 4:

result = 0 XOR 4 = 4

The second element in the array is 1:

result = 4 XOR 1 = 5

The third element in the array is 2:

result = 5 XOR 2 = 7

The fourth element in the array is 1:

result = 7 XOR 1 = 6

The fifth element in the array is 2:

result = 6 XOR 2 = 4

The final value of result is 4 which is the single element in the array.

Let's see the implementation of the solution:

function singleNumber(nums) {
  let result = 0;
  for (let i = 0; i < nums.length; i++) {
    result ^= nums[i];
  }
  return result;
}

This implementation has a time complexity of O(n) as we are iterating over the entire array. It also has a space complexity of O(1) as we are not using any extra space.

1