Sum Of Two Integers - Leetcode Solution

Problem:

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1: Input: a = 1, b = 2 Output: 3

Example 2: Input: a = -2, b = 3 Output: 1

Solution:

The problem statement says that we are not allowed to use + and - operators to find the sum of two integers. So we can use the bitwise operators to achieve this.

We need to perform bitwise addition and also take care of carry operations. For bitwise addition, we can use the XOR operator (^) which gives us the sum without considering carry. For carry operations, we can use the AND operator (&) and then shift it one position to the left.

The algorithm to calculate the sum of two integers a and b without using the + and - operators can be summarized as follows:

1. Initialize the carry variable as 0.
2. Loop over until b becomes 0, i.e. there is no carry left.
3. Find the sum using XOR operator and carry using AND operator.
4. Shift the carry one position to the left.
5. Assign the sum to a.
6. Assign the carry to b.
7. Return the result.

Let's implement the above algorithm in Python:

def getSum(a: int, b: int) -> int: # 32-bit Integer Max Value MAX = 0x7FFFFFFF # 32-bit Integer Min Value MIN = 0x80000000 # Mask to extract the last 32 bits MASK = 0xFFFFFFFF

# Loop until there is no carry left
while b != 0:

    # Calculate the sum without considering carry
    sum = (a ^ b) & MASK
    # Calculate the carry
    carry = ((a & b) << 1) & MASK

    # Update the values of a and b
    a = sum
    b = carry

# If the sum is negative, convert it into 32-bit integer
if a > MAX:
    a = ~(a ^ MASK)

# Return the result
return a

Explanation:

We initialize the maximum and minimum values of a 32-bit integer (MAX and MIN) and a mask to extract the last 32 bits (MASK). We then loop over until b becomes 0 which means there is no carry left.

Inside the loop, we calculate the sum using the XOR operator (^) without considering carry and the carry using the AND operator (&) by shifting it one position to the left. We then update the values of a and b with the sum and the carry respectively.

After the loop, we check if the sum is negative, i.e. greater than the maximum 32-bit integer value. If it is, we convert it into a 32-bit integer by using the NOT operator (~) and XORing it with the MASK.

Finally, we return the result.

Time Complexity: O(1)

Space Complexity: O(1)

The time complexity of this algorithm is O(1) because we are simply performing a constant number of operations independent of the inputs size. Similarly, the space complexity is also O(1) because we are not using any extra storage.

1