Skip to main content

🟨 Sum of Two Integers (#371)

🔗 Problem Link​

📋 Problem Statement​

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

💡 Examples​

Example 1​

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

Example 2​

Input: a = 2, b = 3
Output: 5

🔑 Key Insights & Approach​

Core Observation: Use XOR for sum without carry, AND + left shift for carry. Repeat until no carry.

Why XOR and AND?

  • XOR gives sum without carry
  • AND + shift gives carry
  • Repeat until carry is 0

Pattern: "Bitwise Addition" pattern.

🐍 Solution: Python​

Approach: XOR + AND​

Time Complexity: O(1) - at most 32 iterations | Space Complexity: O(1)

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF

        while b != 0:
            sum_without_carry = (a ^ b) & mask
            carry = ((a & b) << 1) & mask
            a = sum_without_carry
            b = carry

        # Handle negative numbers in Python
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)

🔵 Solution: Golang​

Approach: XOR + AND​

Time Complexity: O(1) | Space Complexity: O(1)

func getSum(a int, b int) int {
    for b != 0 {
        carry := (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
}

📚 References​