This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Find the sum of two integers without using the + or - sign.

Constraints

  • Can we assume the inputs are valid?
    • No, check for None
  • Can we assume this fits memory?
    • Yes

Test Cases

* None input -> TypeError
* 5, 7 -> 12
* -5, -7 -> -12
* 5, -7 -> -2

Algorithm

We'll look at the following example, adding a and b:

a 0111 
b 0101

First, add a and b, without worrying about the carry (0+0=0, 0+1=1, 1+1=0):

result = a ^ b = 0010

Next, calculate the carry (1+1=2). We'll need to left shift one to prepare for the next iteration when we move to the next most significant bit:

carry = (a&b) << 1 = 1010

If the carry is not zero, we'll need to add the carry to the result. Recursively call the function, passing in result and carry.

Below are the values of a, b, and the carry of a = 7 and b = 5, producing the result of 12.

a 0111 
b 0101 
----- 
c 0101 
a 0010 
b 1010 
----- 
c 0010 
a 1000 
b 0100 
----- 
c 0000 
a 1100 
b 0000

c = carry = 0, return the result 1100

Complexity:

  • Time: O(b), where b is the number of bits
  • Space: O(b), where b is the number of bits

Code

In [1]:
class Solution(object):

    def sum_two(self, a, b):
        if a is None or b is None:
            raise TypeError('a or b cannot be None')
        result = a ^ b;
        carry = (a&b) << 1
        if carry != 0:
            return self.sum_two(result, carry)
        return result;

Unit Test

In [2]:
%%writefile test_sum_two.py
import unittest


class TestSumTwo(unittest.TestCase):

    def test_sum_two(self):
        solution = Solution()
        self.assertRaises(TypeError, solution.sum_two, None)
        self.assertEqual(solution.sum_two(5, 7), 12)
        self.assertEqual(solution.sum_two(-5, -7), -12)
        self.assertEqual(solution.sum_two(5, -7), -2)
        print('Success: test_sum_two')


def main():
    test = TestSumTwo()
    test.test_sum_two()


if __name__ == '__main__':
    main()
Overwriting test_sum_two.py
In [3]:
%run -i test_sum_two.py
Success: test_sum_two