Problem

Write a method to implement *, – , / operations You should use only the + operator.

Examples

Example 1:

1
2
3

Input: 5 * 3
Output: 15
Explanation: Multiplying 5 by 3 using only addition: 5 + 5 + 5 = 15

Example 2:

1
2
3

Input: 10 - 4
Output: 6
Explanation: Subtracting 4 from 10 using only addition.

Example 3:

1
2
3

Input: 9 / 3
Output: 3
Explanation: Dividing 9 by 3 using only addition.

Solution

Method 1 - Using addition smartly

To implement these operations using only the + operator, and suppose we have 2 numbers a, b:

  1. Multiplication:
    • Multiplication can be implemented using repeated addition.
    • For example, 5 * 3 is 5 + 5 + 5.
  2. Subtraction:
    • Use addition by negating the number being subtracted.
    • For example, 10 - 4 can be thought of as 10 + (-4).
  3. Negation:
    • To implement negation, repeatedly add -1 to zero until the number is reached.
  4. Division:
    • Division can be implemented by repeated subtraction (which uses addition). a / b can be implemented as finding how many times you need to add b, until getting a.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

public class Solution {

    public int negate(int x) {
        int neg = 0;
        int d = x > 0 ? -1 : 1;
        while (x != 0) {
            neg += d;
            x += d;
        }
        return neg;
    }

    public int subtract(int a, int b) {
        return a + negate(b);
    }

    public int multiply(int a, int b) {
        if (a < b) {
            return multiply(b, a);
        }

        int sum = 0;
        for (int i = 0; i < Math.abs(b); i++) {
            sum += a;
        }
        if (b < 0) {
            sum = negate(sum);
        }
        return sum;
    }

    public int divide(int a, int b) {
        if (b == 0) {
            throw new ArithmeticException("Cannot divide by zero");
        }

        int absA = Math.abs(a);
        int absB = Math.abs(b);

        int quotient = 0;
        int sum = 0;
        while (sum + absB <= absA) {
            sum += absB;
            quotient++;
        }

        if ((a > 0 && b < 0) || (a < 0 && b > 0)) {
            quotient = negate(quotient);
        }
        return quotient;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution:
    def negate(self, x: int) -> int:
        neg = 0
        delta = -1 if x > 0 else 1
        while x != 0:
            neg += delta
            x += delta
        return neg
    
    def subtract(self, a: int, b: int) -> int:
        return a + self.negate(b)
    
    def multiply(self, a: int, b: int) -> int:
        if a < b:
            return self.multiply(b, a)
        sum: int = 0
        for _ in range(abs(b)):
            sum += a
        if b < 0:
            sum = self.negate(sum)
        return sum
    
    def divide(self, a: int, b: int) -> int:
        if b == 0:
            raise ArithmeticError("Cannot divide by zero")
        
        absA = abs(a)
        absB = abs(b)
        quotient: int = 0
        sum: int = 0
        while sum + absB <= absA:
            sum += absB
            quotient += 1
        
        if (a > 0 and b < 0) or (a < 0 and b > 0):
            quotient = self.negate(quotient)
        return quotient

Complexity

  • ⏰ Time complexity:
    • Subtraction: O(n) where n is the number to be negated.
    • Multiplication: O(n) where n is the smaller of the two numbers being multiplied.
    • Division: O(n) where n is the magnitude of the dividend.
  • 🧺 Space complexity: O(1) as we are using only a fixed number of additional variables.