Easy: Single Number
March 2, 2023
Problem Statement
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, 3Output: 4
Example 2:
Input: 1, 9, 1Output: 9
Solution
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 and space complexity will also be .
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 (opens in a new tab)
Code
package mainimport ( "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 as we iterate through all numbers of the input once.
Space Complexity: The algorithm runs in constant space .