371. Sum of Two Integers

NeetCode: Sum of Two Integers · LeetCode: 371. Sum of Two Integers · Difficulty: Medium

Return a + b without using the + and - operators for adding the two numbers. The inputs can be negative.

Example

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

Brute force: count up or down by one

Adding b is the same as stepping a upward b times (or downward |b| times if b is negative). The step counter is a long because Math.abs(Integer.MIN_VALUE) is still negative in int. This doesn't use a + b directly, but it takes time proportional to the value of b, which is exponential in its number of bits. The demo keeps values small.

public class Main {
    static class Solution {
        public int getSum(int a, int b) {
            long steps = Math.abs((long) b);
            for (long i = 0; i < steps; i++) {
                if (b > 0) {
                    a++;
                } else {
                    a--;
                }
            }
            return a;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.getSum(1, 2));
        System.out.println(s.getSum(-2, 3));
        System.out.println(s.getSum(-1, 1));
        System.out.println(s.getSum(-5, -6));
    }
}

3
1
0
-11

Time: O(|b|). Space: O(1).

Optimal: XOR is the sum, AND is the carry

Add bit by bit. For one column, a ^ b is the sum bit ignoring carries, and a & b marks where both bits are 1, i.e. where a carry is produced; the carry belongs one position to the left, so shift it: (a & b) << 1. Then a + b equals (a ^ b) + carry, which is the same problem again, so loop with a = a ^ b and b = carry until the carry is 0. Each round pushes the carry at least one position up, so it finishes in at most 32 rounds.

Negative numbers need no special care because int is stored in two's complement, which is exactly the representation this algorithm manipulates. In Java, << on an int silently drops bits shifted out of the top, so a carry that runs off the end disappears, which is the correct wrap-around behavior. The sum itself wraps like + does, so Integer.MAX_VALUE + 1 gives Integer.MIN_VALUE.

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

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.getSum(1, 2));
        System.out.println(s.getSum(-2, 3));
        System.out.println(s.getSum(-1, 1));
        System.out.println(s.getSum(-5, -6));
        System.out.println(s.getSum(Integer.MAX_VALUE, 0));
        System.out.println(s.getSum(Integer.MAX_VALUE, 1)); // wraps to Integer.MIN_VALUE
    }
}

3
1
0
-11
2147483647
-2147483648

Time: O(w) for w = 32 bits, i.e. constant. Space: O(1).