Sum of Two Integers solution and explanation
Google
IBM
9 more videos on this problem
Sum of Two Integers - Leetcode 371 - JavaNeetCode · 11:48 · 188K views
Sum of Two Integers - LeetCode 371 - PythonDeepti Talesra · 15:53 · 12K views
Leetcode 371. Sum of Two Integers. Bit Manipulation [C++ / Java]TECH_ED · 9:15 · 9K views
Google Interview Question - Sum of Two Integers - LeetCode 371AlgoJS · 3:21 · 4K views
Leetcode 371 | Sum of Two Integers | Binary | Bit ManipulationCoding Together · 5:24 · 3K views
Sum Of Two Integers | LeetCode 371 (Medium)Destination FAANG · 15:58 · 2K views
Sum of Two Integers - LeetCode 371 - JavaLeetCode University · 23:12 · 1K views
[Essential LeetCode Questions] #371 Sum of Two Integers| PythonINTJ programmer · 24:40 · 1K views
Sum of Two Integers - LeetCode - 371 Solution C++/ Blind 75 Solutions (Live Coding)IAjayMukhiya · 15:31 · 294 views
Leetcode 371. Sum of Two Integersultcode · 0:45 · 267 views
The problem
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.
def get_sum(a, b):
while b != 0:
carry = a & b
a = a ^ b
b = carry << 1
return a
print(get_sum(2, 3))public class Main {
public static int getSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
public static void main(String[] args) {
System.out.println(getSum(1, 2));
}
}#include <iostream>
int getSum(int a, int b) {
while (b != 0) {
unsigned carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
int main() {
int a = 2, b = 3;
std::cout << getSum(a, b);
return 0;
}function getSum(a, b) {
while (b !== 0) {
let carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
console.log(getSum(1, 2));#include <stdio.h>
int getSum(int a, int b) {
while (b != 0) {
unsigned carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
int main() {
int a = 1, b = 2;
printf("%d", getSum(a, b));
return 0;
}using System;
class Program {
static int GetSum(int a, int b) {
while (b != 0) {
int carry = a & b;
a = a ^ b;
b = carry << 1;
}
return a;
}
static void Main() {
Console.WriteLine(GetSum(2, 3));
}
}Python, being a high-level language, allows easy manipulation of integers. The approach and logic are the same: use ^ for interim sum and & followed by a << 1 for updating the carry.
Time Complexity: O(n), where n is the number of bits.
Space Complexity: O(1).
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.
def get_sum(a, b):
if b == 0:
return a
else:
return get_sum(a ^ b, (a & b) << 1)
print(get_sum(2, 3))public class Main {
public static int getSum(int a, int b) {
if (b == 0) return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}
public static void main(String[] args) {
System.out.println(getSum(1, 2));
}
}#include <iostream>
int getSum(int a, int b) {
if (b == 0) return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}
int main() {
int a = 2, b = 3;
std::cout << getSum(a, b);
return 0;
}function getSum(a, b) {
if (b === 0) return a;
return getSum(a ^ b, (a & b) << 1);
}
console.log(getSum(1, 2));#include <stdio.h>
int getSum(int a, int b) {
if (b == 0) return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return getSum(sum, carry);
}
int main() {
int a = 1, b = 2;
printf("%d", getSum(a, b));
return 0;
}using System;
class Program {
static int GetSum(int a, int b) {
if (b == 0) return a;
int sum = a ^ b;
int carry = (a & b) << 1;
return GetSum(sum, carry);
}
static void Main() {
Console.WriteLine(GetSum(2, 3));
}
}Python's recursive solution handles the addition through a base case check and recursive calls. Each recursive call passes the updated sum and carry until carry is zero.
Time Complexity: O(n), where n is the number of bits.
Space Complexity: O(n), due to recursion depth in the call stack.
Approach 3: Default Approach
func getSum(a int, b int) int {
for b != 0 {
s := a ^ b
b = (a & b) << 1
a = s
}
return a
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitwise Iterative Approach | Time Complexity: O(n), where n is the number of bits. |
| Recursive Bitwise Approach | Time Complexity: O(n), where n is the number of bits. |
| Default Approach | – |
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. |
Frequently asked questions
Is Sum of Two Integers easy or hard?
The problem is rated Medium because the logic is simple once you know the XOR and carry trick, but it requires understanding binary addition and two's complement. Many candidates struggle if they have not practiced bit manipulation problems.
How to solve Sum of Two Integers in O(1)?
Use bitwise operations to simulate binary addition. Compute the partial sum using a XOR b, compute the carry using (a AND b) shifted left by one, and repeat until the carry becomes zero. Since the number of bits is fixed, the number of iterations is constant.
What is the best approach for Sum of Two Integers?
The standard solution uses bit manipulation with XOR and AND operations. XOR computes the partial sum without carry, while AND followed by a left shift computes the carry. Repeating this process until the carry becomes zero produces the final sum in O(1) time and O(1) space.
What data structure is used in Sum of Two Integers?
No external data structure is required. The solution relies purely on bitwise operators such as XOR, AND, and left shift to manipulate the binary representation of integers.
What is the time complexity of Sum of Two Integers?
The optimal solution runs in O(1) time because integers have a fixed number of bits (usually 32). The algorithm performs carry propagation using bit operations, which can occur at most once per bit position.
Sum of Two Integers Python or Java solution approach?
Both Python and Java implementations use the same bitwise logic: compute XOR for the partial sum and AND plus left shift for the carry. Java typically handles 32-bit integers directly, while Python solutions often mask intermediate results to simulate 32-bit two's complement behavior.
Is Sum of Two Integers asked at Google, Amazon, or Meta?
Sum of Two Integers is a common interview problem at companies that test low-level problem solving and bit manipulation. Variations of this question have appeared in interviews at Google, Amazon, and Meta because it checks understanding of binary arithmetic and two's complement representation.