Sum of Two Integers - Solution & Explanation
Problem Statement
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2 Output: 3
Example 2:
Input: a = 2, b = 3 Output: 5
Constraints:
-1000 <= a, b <= 1000
Approach Overview
Problem Overview: Given two integers a and b, return their sum without using the + or - operators. The trick is to simulate how addition works at the bit level using operations from bit manipulation.
Approach 1: Bitwise Iterative Approach (Time: O(1), Space: O(1))
Addition in binary can be separated into two parts: the sum without carry and the carry itself. The XOR operation (a ^ b) gives the partial sum where bits differ, which is exactly how addition behaves without carrying. The AND operation (a & b) identifies positions where both bits are 1, which produces a carry. Shifting this carry left by one ((a & b) << 1) moves it to the correct position for the next addition step.
The algorithm repeatedly computes the partial sum using XOR and the carry using AND + left shift. Then it replaces a with the partial sum and b with the carry. This continues until the carry becomes zero, meaning no more bits need propagation. Because integers are limited to a fixed number of bits (typically 32), the loop runs at most a constant number of times, giving O(1) time complexity.
This approach relies purely on bit-level operations and works for both positive and negative numbers using two's complement representation. It is the standard solution expected when the problem is tagged with math and bit manipulation.
Approach 2: Recursive Bitwise Approach (Time: O(1), Space: O(1))
The same XOR-and-carry logic can be expressed recursively. Compute the partial sum with a ^ b and compute the carry with (a & b) << 1. Instead of looping, call the function again with these two new values. Each recursive call resolves one level of carry propagation.
The base case occurs when the carry becomes zero. At that point, the partial sum already represents the final result and can be returned directly. Since the maximum number of carry propagations is bounded by the number of bits in the integer representation (around 32), the recursion depth is constant.
This version is conceptually elegant because it mirrors how binary addition propagates carries step by step. However, many engineers prefer the iterative version in production code to avoid recursion overhead and keep stack usage minimal.
Recommended for interviews: The iterative bitwise approach is what interviewers usually expect. It demonstrates that you understand how addition works at the binary level and how XOR and AND simulate sum and carry. Mentioning the recursive variation shows deeper understanding, but implementing the iterative version quickly signals strong familiarity with bit manipulation fundamentals.
Approach 1: Bitwise Iterative Approach
This approach imitates the addition mechanism in digital circuits using bitwise operations. The key operations involved are:
- Use XOR (^) to find the sum bits, similar to adding without carrying.
- Use AND (&) followed by a left shift to determine the carry bits, which tells us which positions need a carry to the left.
- Iteratively apply the above two operations until there is no carry left.
The solution utilizes a while-loop that continues until there is no carry left. The carry is calculated as a & b, and the sum without carry is calculated via a ^ b. The carry is then shifted left by one position (as happens in binary addition) and added to 'b' for the next iteration until the carry becomes zero. Each iteration moves the carry one bit to the left (achieved by << 1), imitating the binary addition process.
Complexity
Time Complexity: O(n), where n is the number of bits needed to represent the numbers.
Space Complexity: O(1), constant space usage.
Approach 2: Recursive Bitwise Approach
This approach is an extension of the iterative bitwise method but uses recursive calls to achieve the result. Instead of using a loop, it relies on recursive function calls to process the sum and carry until the carry becomes zero.
- First, calculate the sum without carry using XOR.
- Then, determine the carry using AND, and left shift it.
- Invoke the same method recursively with the new calculated values until carry becomes zero.
In this C solution, the base case for the recursion is when b (carry) becomes zero, at which point a contains the result. sum is calculated using XOR and carry is calculated and shifted. These new values are passed in the next recursive call.
Complexity
Time Complexity: O(n), where n is the number of bits.
Space Complexity: O(n), due to the recursive call stack.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Bitwise Iterative Approach | Time Complexity: O(n), where n is the number of bits needed to represent the numbers. |
| Recursive Bitwise Approach | Time Complexity: O(n), where n is the number of bits. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitwise Iterative Approach | O(1) | O(1) | Best general solution. Preferred in interviews and production due to constant space and clear carry handling. |
| Recursive Bitwise Approach | O(1) | O(1) | Useful for explaining the concept of recursive carry propagation in binary addition. |
Video Solution
Sum of Two Integers - Leetcode 371 - Java • NeetCode • 188,624 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sum of Two Integers easy or hard?
How to solve Sum of Two Integers in O(1)?
What is the best approach for Sum of Two Integers?
What data structure is used in Sum of Two Integers?
What is the time complexity of Sum of Two Integers?
Sum of Two Integers Python or Java solution approach?
Is Sum of Two Integers asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Sum of Two Integers with our built-in code editor and test cases.
Practice on FleetCode