Solution For Sum Of Two Integers

Problem:

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

Solution:

The problem statement says that we are not allowed to use + and – operators to find the sum of two integers. So we can use the bitwise operators to achieve this.

We need to perform bitwise addition and also take care of carry operations. For bitwise addition, we can use the XOR operator (^) which gives us the sum without considering carry. For carry operations, we can use the AND operator (&) and then shift it one position to the left.

The algorithm to calculate the sum of two integers a and b without using the + and – operators can be summarized as follows:

1. Initialize the carry variable as 0.
2. Loop over until b becomes 0, i.e. there is no carry left.
3. Find the sum using XOR operator and carry using AND operator.
4. Shift the carry one position to the left.
5. Assign the sum to a.
6. Assign the carry to b.
7. Return the result.

Let’s implement the above algorithm in Python:

def getSum(a: int, b: int) -> int:
# 32-bit Integer Max Value
MAX = 0x7FFFFFFF
# 32-bit Integer Min Value
MIN = 0x80000000
# Mask to extract the last 32 bits
MASK = 0xFFFFFFFF

# Loop until there is no carry left
while b != 0:

    # Calculate the sum without considering carry
    sum = (a ^ b) & MASK
    # Calculate the carry
    carry = ((a & b) << 1) & MASK

    # Update the values of a and b
    a = sum
    b = carry

# If the sum is negative, convert it into 32-bit integer
if a > MAX:
    a = ~(a ^ MASK)

# Return the result
return a

Explanation:

We initialize the maximum and minimum values of a 32-bit integer (MAX and MIN) and a mask to extract the last 32 bits (MASK). We then loop over until b becomes 0 which means there is no carry left.

Inside the loop, we calculate the sum using the XOR operator (^) without considering carry and the carry using the AND operator (&) by shifting it one position to the left. We then update the values of a and b with the sum and the carry respectively.

After the loop, we check if the sum is negative, i.e. greater than the maximum 32-bit integer value. If it is, we convert it into a 32-bit integer by using the NOT operator (~) and XORing it with the MASK.

Finally, we return the result.

Time Complexity: O(1)

Space Complexity: O(1)

The time complexity of this algorithm is O(1) because we are simply performing a constant number of operations independent of the inputs size. Similarly, the space complexity is also O(1) because we are not using any extra storage.

Step by Step Implementation For Sum Of Two Integers

public class Solution {
    public int getSum(int a, int b) {
        // Iterate till there is no carry  
        while (b != 0) {
            // carry now contains common set bits of x and y
            int carry = a & b;  
 
            // Sum of bits of x and y where at least one of the bits is not set
            a = a ^ b; 
 
            // Carry is shifted by one so that adding it to x gives the required sum
            b = carry << 1;
        }
        return a;
    }
}

def getSum(a, b):
    
    # Base case
    if a == 0:
        return b
        
    # Recursive case
    else:
        return getSum(a-1, b+1)

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var getSum = function(a, b) {
    // bitwise operators only work on 32-bit integers
    // we can use the & operator to check if the last bit is 1
    // we can use the | operator to set the last bit to 1
    // we can use the >> operator to shift the bits to the right
    // we can use the << operator to shift the bits to the left
    
    // we can keep track of the carry by ANDing the two numbers
    // and shifting the carry to the left
    while (b != 0) {
        let carry = a & b;
        a = a ^ b;
        b = carry << 1;
    }
    return a;
};

int getSum(int a, int b) {
     return a + b;
}

public class Solution {
    public int GetSum(int a, int b) {
        // Iterate till there is no carry  
        while (b != 0)
        {
            // carry now contains common set bits of a and b
            int carry = a & b; 
 
            // Sum of bits of a and b where at least one of the bits is not set
            a = a ^ b; 
 
            // Carry is shifted by one so that adding it to a gives the required sum
            b = carry << 1;
        }
        return a;
    }
}