We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Two Integers

Difficulty: Medium

Problem Description

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

Key Insights

  • The sum of two integers can be computed using bitwise operations.
  • The XOR operation can be used to calculate the sum without carrying.
  • The AND operation followed by a left shift can determine the carry.
  • The process can be repeated until there are no carries left.

Space and Time Complexity

Time Complexity: O(1) - The number of operations is constant since the range of integers is fixed. Space Complexity: O(1) - No additional space is used that scales with input size.

Solution

To solve the problem, we can use bit manipulation. The main idea is to use bitwise XOR to add the numbers without carrying and to use bitwise AND along with a left shift to calculate the carry. We repeat this process until there are no carries left.

  1. Calculate the sum without carrying using XOR (a ^ b).
  2. Calculate the carry using AND and shift it left ((a & b) << 1).
  3. Update a to the sum and b to the carry.
  4. Repeat until there is no carry (i.e., b is 0).

Code Solutions

def getSum(a: int, b: int) -> int:
    while b != 0:
        # Calculate sum without carry
        sum_without_carry = a ^ b
        # Calculate carry
        carry = (a & b) << 1
        # Update a and b
        a = sum_without_carry
        b = carry
    return a
← Back to All Questions