Single Number

Problem Statement

Given a non-empty array of integers nums, every element appears twice except for one. Find the element which appeared once in the array.

Example 1

nums   = [1, 1, 9, 9, 2, 2, 3]
output = 8

Example 2

nums   = [1, 2, 2, 3, 3, 1, 5, 8, 5]
output = 8

Example 3

nums   = [-12, 23, 23, -8, -12, 0, 0] 
output = 8

Constraints:

1 <= nums.length <= 3 * 100
-3 100 <= nums[i] <= 3 100
Each element in the array appears twice except for one element which appears only once.

Solution

Brute Force Solution

Simple logic to solve this problem is to use nested loops and check if every element exists twice. Here's the pseudo-code of the solution using a nested loop.

FOR i=0 to len(nums) :

    notFound = true

    FOR j=0 to len(nums):

        IF nums[i] == nums[j] and i != j:
            notFound = false

    IF notFOund :
        return nums[i]

In the worst-case condition, the Runtime complexity of the above approach would be O(N^2) and space complexity would be O(1). You can find the golang implementation of above here

Optimized Approach I

We can improve the run time complexity if we can keep the count of all the elements encountered in the nums array. We can keep the count using two different data structures, i.e, Array and Hash Map

Array : Since, Elements of nums array lies between, -300 to 300, We can create array of size 601 and store counts in the array. For example -300 at countArray[0], -299 at countArray[1], -298 at countArray[2] and so on.
Hash Map: We can store the elements as the key of the map and the count of the element as the value of the map.

Pseudocode (Using Array)

INT countArray[601]

FOR each element in nums:

    currElement = nums[i]
    countArray[currElement+300] += 1 
    //need to add the offset 300 so that -300 maps to index 0

FOR index 0 to 601:

    IF countArray at index == 1:
        //need to subtract the offset 300 so that we can retrieve the correct element.
        return index-300

Pseudocode (Using Hash Map)

MAP countMap[INT]INT

FOR each element in nums:    
    countMap[element] += 1


FOR each element in nums:
    count = countMap[element] 

    IF count == 1:
        return element

Using the above two approaches we can reduce the runtime complexity of the solution to O(N). The above approach is reducing the time complexity but it will increase the space complexity of the solution. Since we are using extra space to create a map/array, which will store N/2 elements.

Optimized Approach II

Although we improved the runtime complexity of our code in our previous approach, we had to use extra space.

We can further optimize the code by using the XOR operation between all the elements.

XOR is boolean operator which return 0 if the we perform XOR with number itself, i.e, 5 ^ 5 => 0.

You can find more about XOR operator from Binary Operators in Golang

We can XOR all the elements of the array with itself, all the duplicate elements will result in 0 after the XOR operation, At the end, we will get the number that occurred only once.

Explanation

1   nums = [2,3,4,5,6,2,3,4,5]
2   
3   result = 0
4   result = 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 2 ^ 3 ^ 4 ^ 5
5   
6   result = (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) ^ (5 ^ 5) ^ 6
7   result =    0    ^    0    ^    0    ^    0    ^ 6
8   result =    0 ^ 6
9   result = 6

Let's say we have nums array [2,3,4,5,6,2,3,4,5], we start taking XOR of each element in the array in line 4. As we can see in line 6, If we just re-arrange the elements we will get 0 as a result of all the XOR operations except for the element which is occurring once. Since 0 ^ X will always return X. We can surely say that the result variable will store the number which only occurred once

Pseudocode (Using XOR)

result = 0

FOR each number in nums:
    result = result XOR number

return result

Here's the Golang implementation of the above pseudo-code:


func singleNumber(nums []int) int {

    var result int

    for _, num := range nums {
        result = result ^ num 
    }

    return result
}

You can find the complete code here