Easy: Single Number

1 min read Tweet this post

In a non-empty array of integers, every number appears twice except for one, find that single number.

Example 1:

Input: 1, 4, 6, 1, 3, 6, 3
Output: 4

Example 2:

Input: 1, 9, 1
Output: 9

The simple solution is using a hashmap and iterate through the input:

  • if number already in the hashmap, remove it
  • if number is not present in hashmap, add it
  • in the end, only left 1 data in the hashmap

Time and space Complexity: Time Complexity of the above solution will be O(n)O(n) and space complexity will also be O(n)O(n).

Section titled Can we do better than this using the XOR Pattern?

Can we do better than this using the XOR Pattern?

Recall the following two properties of XOR:

  • It returns zero if we take XOR of two same numbers.
  • It returns the same number if we XOR with zero. So we can XOR all the numbers in the input; duplicate numbers will zero out each other and we will be left with the single number.

Try it yourself https://go.dev/play/p/XcOwP-nIMDO

package main

import (
	"testing"
)

func FindSingleNumber(list []int) int {
	num := 0
	for i := range list {
		num ^= list[i]
	}

	return num
}

func TestLastIndex(t *testing.T) {
	tests := []struct {
		list []int
		want int
	}{
		{list: []int{1, 4, 2, 1, 3, 2, 3}, want: 4},
		{list: []int{1, 9, 1}, want: 9},
	}
	for _, tt := range tests {
		if got := FindSingleNumber(tt.list); got != tt.want {
			t.Errorf("LastIndex(%v) = %v, want %v", tt.list, got, tt.want)
		}
	}
}

Time Complexity: Time complexity of this solution is O(n)O(n) as we iterate through all numbers of the input once.

Space Complexity: The algorithm runs in constant space O(1)O(1).

grokking algorithm go pattern xor