LeetCode Solution 371 - Sum of Two Integers

Problem Statement

Given two integers a and b, return the sum of the two integers without using the + and - operators.

Example 1:

Input:

a = 1, b = 2

Output:

3

Example 2:

Input:

a = -1, b = 1

Output:

0

---

Optimal Approach: Bit Manipulation (Using Bitwise Operators)

Why Bit Manipulation?

• We can add two numbers without using + or - by utilizing bitwise XOR and bitwise AND with left shift.
• XOR (^) calculates the sum without carrying.
• AND (&) followed by left shift (<<) determines the carry.
• Iteratively update a and b until no carry remains.

Algorithm:

1. While b is nonzero:
   • Compute the carry as (a & b) << 1.
   • Compute the sum as a ^ b.
   • Update a = sum, b = carry.
2. Return a as the final result.

---

C++ Code Implementation

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

---

Step-by-Step Explanation

1. Initialize a and b.
2. Loop until b becomes 0 (no more carry).
   • carry = (a & b) << 1 (Calculate carry bits and shift left).
   • a = a ^ b (Compute sum without carrying).
   • b = carry (Update b to carry).
3. Return a as the final sum.

---

Dry Run

Input:

a = 3, b = 5

Execution:

Step	a	b	a & b	Carry (a & b) << 1	Sum a ^ b	Updated a	Updated b
1	3	5	1	2	6	6	2
2	6	2	2	4	4	4	4
3	4	4	4	8	0	0	8
4	0	8	0	0	8	8	0
Result	8	0	-	-	-	8	0

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Iterative Addition	O(N)	O(1)	Not allowed to use + or -
Recursion	O(N)	O(N)	Extra function calls increase memory usage
Bit Manipulation (Best)	O(1)	O(1)	Fast and efficient

---

Complexity Analysis

• Time Complexity: O(1) in most cases, as integers have a fixed number of bits (32-bit or 64-bit).
• Space Complexity: O(1), as only a few extra variables are used.

---

Conclusion

• Best Approach: Bit Manipulation.
• Further Practice:
  • Add Binary
  • Single Number

This solution efficiently computes Sum of Two Integers using Bitwise Operations, making it optimal for large numbers without using + or - operators.