Leetcode #371: Sum of Two Integers

LeetCode Solutions

https://leetcode.com/problems/sum-of-two-integers/description/

One approach is to use the concept of bitwise operations to perform addition operation. In binary representation, addition can be performed using XOR (^) operation, while carry can be performed using AND (&) operation. We can keep adding the carry obtained from AND operation to the result obtained from XOR operation until carry becomes zero.

Steps:

  1. Loop until carry becomes zero
  2. XOR a and b to get the result
  3. AND a and b to get the carry
  4. Shift the carry one bit to the left (multiply by 2)
  5. Set a to the result and b to the carry
  6. Continue the loop until the carry becomes zero
  7. Return the result

Here is the solution in python3:

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # 32 bits interger min
        MIN = 0x80000000
        # mask to get last 32 bits
        mask = 0xFFFFFFFF
        while b != 0:
            # XOR operation returns sum without carry
            # AND operation returns carry without sum
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        # if a is negative, then result is 2's complement of (a & MAX)
        return a if a <= MAX else ~(a ^ mask)

Time and Space Complexity

The time complexity of the solution is O(1) since the while loop runs at most 32 times, which is a constant time. In each iteration, the bitwise operators take constant time.

The space complexity is also O(1) since we are not using any extra data structures to store information. We are simply using two variables to keep track of the calculations.