Sum of Two Integers - LeetCode 371 Solution in python

Sum of Two Integers medium

Problem Statement

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

Steps and Explanation

The core idea is to use bit manipulation to simulate addition. We can break down addition into several steps:

Bitwise AND (&): This operation identifies the carry bits. Whenever both bits in a and b are 1, there's a carry. The result is stored in carry.
Bitwise XOR (^): This operation simulates the addition without considering carries. It gives the sum of the bits without carrying. The result is stored in sum.
Left Shift (<<): The carry bits need to be shifted one position to the left to be added in the next iteration.
Iteration: We repeat steps 1-3 until there are no more carry bits (carry == 0).

Let's illustrate with an example: a = 3 (binary 0011), b = 5 (binary 0101)

| Iteration | a | b | carry | sum | | --------- | -------- | -------- | -------- | -------- | | 1 | 0011 | 0101 | 0001 | 0110 | | 2 | 0110 | 0001 | 0010 | 0100 | | 3 | 0100 | 0010 | 0000 | 0110 |

After 3 iterations, carry is 0, and sum is 0110 (decimal 6), which is the correct answer.

Code (Java)

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b; // Find carry bits
            a = a ^ b;          // Sum without carry
            b = carry << 1;    // Shift carry to the left
        }
        return a;
    }
}

Complexity Analysis

Time Complexity: O(log n), where n is the magnitude of the larger integer. The number of iterations is proportional to the number of bits needed to represent the integers.
Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size.