Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 40
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.

For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.

Do this in O(N) time and O(1) space.

Pull request description:
Day40
Resolves #87.

Patch:
diff --git a/README.md b/README.md
index 4ec99d9..e1c7e73 100644
--- a/README.md
+++ b/README.md
@@ -50,3 +50,4 @@ problems from
 * [Day 36](https://github.com/vaskoz/dailycodingproblem-go/issues/79)
 * [Day 37](https://github.com/vaskoz/dailycodingproblem-go/issues/81)
 * [Day 38](https://github.com/vaskoz/dailycodingproblem-go/issues/83)
+* [Day 40](https://github.com/vaskoz/dailycodingproblem-go/issues/87)
diff --git a/day40/problem.go b/day40/problem.go
new file mode 100644
index 0000000..b05344c
--- /dev/null
+++ b/day40/problem.go
@@ -0,0 +1,33 @@
+package day40
+
+// FindOnce returns the number that appears only once in a list where
+// other numbers appear 3 times.
+// Runs in O(N) time and O(1) space.
+func FindOnce(nums []int) int {
+	var ones, twos int
+	for _, v := range nums {
+		twos |= ones & v
+		ones ^= v
+		not := ^(ones & twos)
+		ones &= not
+		twos &= not
+	}
+	return ones
+}
+
+// FindOnceMap uses a map to find the non-duplicated value.
+// Runs in O(N) and O(N) space
+func FindOnceMap(nums []int) int {
+	counts := make(map[int]int)
+	for _, v := range nums {
+		counts[v]++
+	}
+	var result int
+	for k, v := range counts {
+		if v == 1 {
+			result = k
+			break
+		}
+	}
+	return result
+}


Test patch:
diff --git a/day40/problem_test.go b/day40/problem_test.go
new file mode 100644
index 0000000..e4cc156
--- /dev/null
+++ b/day40/problem_test.go
@@ -0,0 +1,45 @@
+package day40
+
+import "testing"
+
+var testcases = []struct {
+	input    []int
+	expected int
+}{
+	{[]int{6, 1, 3, 3, 3, 6, 6}, 1},
+	{[]int{13, 19, 13, 13}, 19},
+}
+
+func TestFindOnce(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := FindOnce(tc.input); tc.expected != result {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkFindOnce(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindOnce(tc.input)
+		}
+	}
+}
+
+func TestFindOnceMap(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := FindOnceMap(tc.input); tc.expected != result {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkFindOnceMap(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			FindOnceMap(tc.input)
+		}
+	}
+}