Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 74
Good morning! Here's your coding interview problem for today.

This problem was asked by Apple.

Suppose you have a multiplication table that is N by N. That is, a 2D array where the value at the i-th row and j-th column is `(i + 1) * (j + 1)` (if 0-indexed) or `i * j` (if 1-indexed).

Given integers N and X, write a function that returns the number of times X appears as a value in an N by N multiplication table.

For example, given N = 6 and X = 12, you should return 4, since the multiplication table looks like this:
```
| 1 | 2 | 3 | 4 | 5 | 6 |

| 2 | 4 | 6 | 8 | 10 | 12 |

| 3 | 6 | 9 | 12 | 15 | 18 |

| 4 | 8 | 12 | 16 | 20 | 24 |

| 5 | 10 | 15 | 20 | 25 | 30 |

| 6 | 12 | 18 | 24 | 30 | 36 |
```
And there are 4 12's in the table.

Pull request:
Day74
Resolves #157.

Patch:
diff --git a/README.md b/README.md
index d867626..a8d7631 100644
--- a/README.md
+++ b/README.md
@@ -83,3 +83,4 @@ problems from
 * [Day 71](https://github.com/vaskoz/dailycodingproblem-go/issues/151)
 * [Day 72](https://github.com/vaskoz/dailycodingproblem-go/issues/153)
 * [Day 73](https://github.com/vaskoz/dailycodingproblem-go/issues/155)
+* [Day 74](https://github.com/vaskoz/dailycodingproblem-go/issues/157)
diff --git a/day74/problem.go b/day74/problem.go
new file mode 100644
index 0000000..950dfe2
--- /dev/null
+++ b/day74/problem.go
@@ -0,0 +1,31 @@
+package day74
+
+// MultiplicationTableBrute counts the number of X occurrences
+// in a N by N multiplication table.
+// Runs in O(N^2) time.
+func MultiplicationTableBrute(N, X int) int {
+	count := 0
+	for i := 1; i <= N; i++ {
+		for j := 1; j <= N; j++ {
+			if i*j == X {
+				count++
+			}
+		}
+	}
+	return count
+}
+
+// MultiplicationTableLinear counts the number of X occurrences
+// in a N by N multiplication table.
+// Runs in O(N) time.
+func MultiplicationTableLinear(N, X int) int {
+	count := 0
+	for i := 1; i <= N; i++ {
+		if i > X {
+			break
+		} else if X%i == 0 && X/i <= N {
+			count++
+		}
+	}
+	return count
+}


Test patch:
diff --git a/day74/problem_test.go b/day74/problem_test.go
new file mode 100644
index 0000000..1997d9b
--- /dev/null
+++ b/day74/problem_test.go
@@ -0,0 +1,48 @@
+package day74
+
+import "testing"
+
+var testcases = []struct {
+	N, X     int
+	expected int
+}{
+	{6, 12, 4},
+	{6, 36, 1},
+	{6, 37, 0},
+	{6, 29, 0},
+	{1000, 29, 2},
+}
+
+func TestMultiplicationTableBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MultiplicationTableBrute(tc.N, tc.X); result != tc.expected {
+			t.Errorf("Given N=%d X=%d got %d expected %d", tc.N, tc.X, result, tc.expected)
+		}
+	}
+}
+
+func BenchmarkMultiplicationTableBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MultiplicationTableBrute(tc.N, tc.X)
+		}
+	}
+}
+
+func TestMultiplicationTableLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MultiplicationTableLinear(tc.N, tc.X); result != tc.expected {
+			t.Errorf("Given N=%d X=%d got %d expected %d", tc.N, tc.X, result, tc.expected)
+		}
+	}
+}
+
+func BenchmarkMultiplicationTableLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MultiplicationTableLinear(tc.N, tc.X)
+		}
+	}
+}