Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 140
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given an array of integers in which two elements appear exactly once and all other elements appear exactly twice, find the two elements that appear only once.

For example, given the array `[2, 4, 6, 8, 10, 2, 6, 10]`, return 4 and 8. The order does not matter.

Follow-up: Can you do this in linear time and constant space?

Pull request:
Day140
Resolves #292.

Patch:
diff --git a/README.md b/README.md
index f64c2d9..f7d7a15 100644
--- a/README.md
+++ b/README.md
@@ -149,3 +149,4 @@ problems from
 * [Day 137](https://github.com/vaskoz/dailycodingproblem-go/issues/285)
 * [Day 138](https://github.com/vaskoz/dailycodingproblem-go/issues/286)
 * [Day 139](https://github.com/vaskoz/dailycodingproblem-go/issues/288)
+* [Day 140](https://github.com/vaskoz/dailycodingproblem-go/issues/292)
diff --git a/day140/problem.go b/day140/problem.go
new file mode 100644
index 0000000..1468ecb
--- /dev/null
+++ b/day140/problem.go
@@ -0,0 +1,57 @@
+package day140
+
+import (
+	"sort"
+)
+
+// SingleOccurrenceBrute returns numbers that occur only once.
+// Runs in O(N log N) time and O(1) space.
+func SingleOccurrenceBrute(nums []int) []int {
+	if len(nums) == 0 {
+		return nil
+	} else if len(nums) == 1 {
+		return nums
+	}
+	sort.Ints(nums)
+	var results []int
+	last := nums[0]
+	count := 1
+	for i := 1; i < len(nums); i++ {
+		if nums[i] != last && count == 1 {
+			results = append(results, nums[i-1])
+			last = nums[i]
+			count = 0
+		} else if nums[i] != last {
+			last = nums[i]
+			count = 0
+		}
+		count++
+	}
+	return results
+}
+
+// SingleOccurrenceLinear returns numbers that occur only once.
+// Runs in O(N) time and O(1) space.
+// Only works if the repeating elements only repeat twice and
+// if only 2 numbers occur once.
+func SingleOccurrenceLinear(nums []int) []int {
+	if len(nums) == 0 {
+		return nil
+	} else if len(nums) == 1 {
+		return nums
+	}
+	xor := nums[0]
+	for i := 1; i < len(nums); i++ {
+		xor ^= nums[i]
+	}
+	results := make([]int, 2)
+	rightMost := xor & ^(xor - 1)
+	for i := range nums {
+		if nums[i]&rightMost != 0 {
+			results[0] ^= nums[i]
+		} else {
+			results[1] ^= nums[i]
+		}
+	}
+	return results
+}


Test patch:
diff --git a/day140/problem_test.go b/day140/problem_test.go
new file mode 100644
index 0000000..473d375
--- /dev/null
+++ b/day140/problem_test.go
@@ -0,0 +1,50 @@
+package day140
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	nums, singleOccurrence []int
+}{
+	{[]int{2, 4, 6, 8, 10, 2, 6, 10}, []int{4, 8}},
+	{[]int{}, nil},
+	{[]int{5}, []int{5}},
+}
+
+func TestSingleOccurrenceBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		copied := append([]int{}, tc.nums...)
+		if result := SingleOccurrenceBrute(copied); !reflect.DeepEqual(result, tc.singleOccurrence) {
+			t.Errorf("Expected %v got %v", tc.singleOccurrence, result)
+		}
+	}
+}
+
+func BenchmarkSingleOccurrenceBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			copied := append([]int{}, tc.nums...)
+			SingleOccurrenceBrute(copied)
+		}
+	}
+}
+
+func TestSingleOccurrenceLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SingleOccurrenceLinear(tc.nums); !reflect.DeepEqual(result, tc.singleOccurrence) {
+			t.Errorf("Expected %v got %v", tc.singleOccurrence, result)
+		}
+	}
+}
+
+func BenchmarkSingleOccurrenceLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SingleOccurrenceBrute(tc.nums)
+		}
+	}
+}