Solution to problem 136 “Single Number” from LeetCode.

Problem Statement

Given a non-empty array of integers. All numbers appear twice except for one number. You need to find this number.

Note: The algorithm should have linear complexity (O(1)). Is it possible to do this without additional memory?

Example

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

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

Solution

Sort the array =)

Algorithm idea:

Sort the input array. Then iterate through the array skipping every other number. At each step, compare the current element with the next one. If they are not equal - then the current one is the unique number we’re looking for.

func singleNumber(nums []int) int {
    sort(nums)
    for idx:=0;idx<len(nums)-2;idx+=2 {
        if nums[idx]!=nums[idx+1] {
            return nums[idx]
        }
    }
    return nums[len(nums)-1]
}


func sort (nums []int) {
    for idx := range nums {
        k := idx
        for jdx := idx-1;jdx>=0;jdx-- {
            if nums[jdx]>nums[k] {
                nums[jdx],nums[k] = nums[k], nums[jdx]
                k = jdx
            }
        }
    }
}

Counting Elements

Algorithm idea:

Create a collection number<->number of occurrences. Iterate through the original array, recording encountered numbers in the collection (incrementing the number of times encountered).

Iterate through the collection looking for an element that appeared only once.

func singleNumber(nums []int) int {
    q:= make(map[int]int,0)

    for idx:=0;idx<len(nums);idx++ {
        if _,ok := q[nums[idx]];!ok {
            q[nums[idx]] = 0
        }
       q[nums[idx]]++
    }

    for idx:=range q {
        if q[idx] == 1 {
            return idx
        }
    }
    return 0
}

XOR

Algorithm idea:

It is known that the xor operation of two identical numbers equals zero. Since all numbers in our array (except one) appear exactly twice – we can XOR the entire array – getting the number we’re looking for.

func singleNumber(nums []int) int {
    for idx:=1;idx<len(nums);idx++ {
       nums[0] = nums[0] ^  nums[idx]
    }
    return nums[0]
}