algoadvance

Leetcode 371. Sum of Two Integers

Problem Statement

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

Clarifying Questions

  1. Are the integers limited to a specific range?
    • The integers are within the range of typical 32-bit signed integers.
  2. Should the solution handle negative numbers?
    • Yes, the solution should handle both positive and negative integers.
  3. Can we use other arithmetic operators like * or /?
    • The problem specifically restricts the use of + and -, but doesn’t mention other operators. However, ideally, we should avoid using any direct arithmetic operators to simulate addition.

Strategy

This problem can be solved by using bitwise operations. The process involves two key operations:

  1. XOR (^) Operation:
    • The XOR operation can be used to add two numbers without considering the carry. The result will be the sum of the bits where at least one of the bits is 1.
  2. AND (&) and Shift («) Operations:
    • The AND operation followed by a left shift is used to find the carry. The carry must be added to the result obtained from the XOR operation until there is no carry left.

Step-by-Step Approach:

  1. Compute the XOR of a and b and store it in a. This gives the sum of a and b without the carry.
  2. Compute the carry using a & b and left shift it by 1 (<< 1).
  3. Update b with the carry.
  4. Repeat the process until b becomes zero.

Code

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            // Calculate the sum without carry
            int sum = a ^ b;
            
            // Calculate the carry
            int carry = (a & b) << 1;
            
            // Update a to sum and b to carry
            a = sum;
            b = carry;
        }
        return a;
    }
};

Time Complexity

This solution utilizes bitwise operations to perform the addition iteratively and efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI