Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 88
Good morning! Here's your coding interview problem for today.

This question was asked by ContextLogic.

Implement division of two positive integers without using the division, multiplication, or modulus operators. Return the quotient as an integer, ignoring the remainder.

Pull request:
Day88
Resolves #185.

Patch:
diff --git a/README.md b/README.md
index 9c685f4..fc4f1e4 100644
--- a/README.md
+++ b/README.md
@@ -97,3 +97,4 @@ problems from
 * [Day 85](https://github.com/vaskoz/dailycodingproblem-go/issues/179)
 * [Day 86](https://github.com/vaskoz/dailycodingproblem-go/issues/181)
 * [Day 87](https://github.com/vaskoz/dailycodingproblem-go/issues/183)
+* [Day 88](https://github.com/vaskoz/dailycodingproblem-go/issues/185)
diff --git a/day88/problem.go b/day88/problem.go
new file mode 100644
index 0000000..2af42b8
--- /dev/null
+++ b/day88/problem.go
@@ -0,0 +1,64 @@
+package day88
+
+import (
+	"errors"
+)
+
+var errDivideByZero = errors.New("can't divide by zero")
+
+// ErrDivideByZero is the error returned if you attempt to divide by zero.
+func ErrDivideByZero() error {
+	return errDivideByZero
+}
+
+// BruteForceDivision calculates the division by looping subtraction.
+// Runs in O(Quotient) time and O(1) space.
+// Returns an error if divisor is zero.
+func BruteForceDivision(dividend, divisor int32) (int32, error) {
+	if divisor == 0 {
+		return 0, ErrDivideByZero()
+	}
+	negative := (dividend < 0 && divisor > 0) || (dividend >= 0 && divisor < 0)
+	dividend = abs(dividend)
+	divisor = abs(divisor)
+	quotient := int32(0)
+	for dividend >= divisor {
+		dividend -= divisor
+		quotient++
+	}
+	if negative {
+		return -quotient, nil
+	}
+	return quotient, nil
+}
+
+// BitShiftDivision calculates the division by bit-shifting.
+// Runs in O(1) time because it loops over 63-bits and O(1) space.
+// Returns an error if divisor is zero.
+func BitShiftDivision(dividend, divisor int32) (int32, error) {
+	if divisor == 0 {
+		return 0, ErrDivideByZero()
+	}
+	negative := (dividend < 0 && divisor > 0) || (dividend >= 0 && divisor < 0)
+	dividend = abs(dividend)
+	divisor = abs(divisor)
+	var quotient, tmp int64
+	for i := uint(31); i < 32; i-- {
+		if tmp+(int64(divisor)<<i) <= int64(dividend) {
+			tmp += int64(divisor) << i
+			quotient |= int64(1) << i
+		}
+	}
+	if negative {
+		return -int32(quotient), nil
+	}
+	return int32(quotient), nil
+}
+
+// abs returns the absolute value.
+func abs(val int32) int32 {
+	if val < 0 {
+		return -val
+	}
+	return val
+}


Test patch:
diff --git a/day88/problem_test.go b/day88/problem_test.go
new file mode 100644
index 0000000..a8f86d7
--- /dev/null
+++ b/day88/problem_test.go
@@ -0,0 +1,47 @@
+package day88
+
+import "testing"
+
+var testcases = []struct {
+	dividend, divisor, quotient int32
+	expectedError               error
+}{
+	{100, 10, 10, nil},
+	{100, -10, -10, nil},
+	{100, 0, 0, ErrDivideByZero()},
+	{1000000, 1, 1000000, nil},
+}
+
+func TestBruteForceDivision(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := BruteForceDivision(tc.dividend, tc.divisor); result != tc.quotient || err != tc.expectedError {
+			t.Errorf("Expected %v,%v got %v,%v", tc.quotient, tc.expectedError, result, err)
+		}
+	}
+}
+
+func BenchmarkBruteForceDivision(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BruteForceDivision(tc.dividend, tc.divisor)
+		}
+	}
+}
+
+func TestBitShiftDivision(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result, err := BitShiftDivision(tc.dividend, tc.divisor); result != tc.quotient || err != tc.expectedError {
+			t.Errorf("Expected %v,%v got %v,%v", tc.quotient, tc.expectedError, result, err)
+		}
+	}
+}
+
+func BenchmarkBitShiftDivision(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BitShiftDivision(tc.dividend, tc.divisor)
+		}
+	}
+}