Add Two Integers
EasyPrompt
num1 and num2, return the sum of the two integers.
Example 1:
Input: num1 = 12, num2 = 5
Output: 17
Explanation: num1 is 12, num2 is 5, and their sum is 12 + 5 = 17, so 17 is returned.Example 2:
Input: num1 = -10, num2 = 4
Output: -6
Explanation: num1 + num2 = -6, so -6 is returned.
Constraints:
-100 <= num1, num2 <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
The most efficient, simple, and idiomatic approach is to use the language's built-in addition operator (+). This is the intended solution for a real-world scenario.
Algorithm
- Add
num1andnum2using the+operator. - Return the result.
Walkthrough
This solution leverages the computer's hardware for maximum performance. Processors have a specialized component, the Arithmetic Logic Unit (ALU), which is designed to perform arithmetic operations like addition extremely quickly, often in a single clock cycle. The + operator in Java (and most other languages) compiles down to a single machine instruction that utilizes the ALU. Therefore, return num1 + num2; is the most optimal way to compute the sum.
class Solution { public int sum(int num1, int num2) { return num1 + num2; }}Complexity
Time
O(1). The addition is a single, highly optimized hardware instruction.
Space
O(1). No additional space is used beyond what's needed to store the inputs and the return value.
Trade-offs
Pros
Maximum efficiency and performance.
Extremely simple, readable, and maintainable code.
This is the standard, idiomatic way to perform addition.
Cons
If the problem is posed in an interview to test knowledge of bit manipulation, this solution would miss the point.
This approach calculates the sum of two integers using bitwise operations, implemented recursively. It's a classic method to perform addition without using the + operator, often used to test a candidate's understanding of low-level binary arithmetic.
Algorithm
- Define a recursive function
sum(a, b). - If
bis 0, it means there are no more carries to process. Returna. - Otherwise, calculate the sum without carry:
sum_without_carry = a ^ b. - Calculate the carry:
carry = (a & b) << 1. - Make a recursive call with the new values:
sum(sum_without_carry, carry).
Walkthrough
The fundamental principle is to mimic the manual process of binary addition. We break down the problem into two simpler parts: calculating the sum as if there were no carries, and calculating the carries themselves.
- The sum of bits at each position, ignoring carries, is equivalent to the bitwise XOR (
^) operation. - A carry is generated at a bit position only if both corresponding bits are 1. This is captured by the bitwise AND (
&) operation. These carries must then be shifted one position to the left (<< 1) to be added to the next significant bit.
The function then recursively calls itself with the new sum and the calculated carries. The base case for the recursion is when the carry becomes zero, at which point the other number holds the final result.
class Solution { public int sum(int num1, int num2) { // Base case: if the second number (which will hold the carry) is 0, // the first number holds the final sum. if (num2 == 0) { return num1; } // Recursive step: // num1 ^ num2 is the sum without considering carries. // (num1 & num2) << 1 is the carry. return sum(num1 ^ num2, (num1 & num2) << 1); }}Complexity
Time
O(k), where `k` is the number of bits in the integer type (e.g., 32 for `int`). In the worst case, a carry can propagate from the least significant bit to the most significant bit, leading to `k` recursive calls. For fixed-size integers, this is considered O(1).
Space
O(k), due to the recursion call stack, where `k` is the number of bits in the integer. The depth of the recursion can be up to `k`. For fixed-size integers like Java's `int`, this is effectively O(1).
Trade-offs
Pros
Excellent for demonstrating a deep understanding of binary arithmetic and bitwise operators.
Works correctly for negative numbers due to the properties of two's complement representation.
Cons
Less efficient than direct addition due to the overhead of multiple function calls.
Can lead to a stack overflow if the recursion depth is too large (not an issue for standard 32/64-bit integers).
Code is more complex and less intuitive than a simple
+operation.
This approach uses the same bitwise logic as the recursive method but implements it within a loop. By avoiding recursion, it eliminates the overhead of function calls and the risk of stack overflow, making it slightly more efficient.
Algorithm
- Initialize a loop that continues as long as
num2is not 0. - Inside the loop, compute the carry:
carry = (num1 & num2) << 1. - Update
num1to the sum without carry:num1 = num1 ^ num2. - Update
num2to be thecarry. - After the loop,
num1holds the final sum. Returnnum1.
Walkthrough
The algorithm iteratively computes the sum. In each iteration, it calculates the carry and the sum-without-carry. The sum-without-carry replaces one of the numbers, and the carry replaces the other. The loop continues until the carry becomes zero.
- A
whileloop runs as long as the second number (num2, which we use to track the carry) is not zero. - Inside the loop, we first calculate the
carry. The carry is(num1 & num2)shifted left by one bit. We must store this in a temporary variable because we need the originalnum2to calculate the newnum1. - Next, we update
num1to be the sum of bits without carry:num1 = num1 ^ num2. - Finally, we update
num2to be thecarrywe calculated, preparing for the next iteration. - Once the loop terminates (
num2is 0),num1holds the complete sum.
class Solution { public int sum(int num1, int num2) { while (num2 != 0) { // Calculate carry and shift it to the left int carry = (num1 & num2) << 1; // Calculate sum of bits without carry num1 = num1 ^ num2; // Move carry to num2 to be added in the next iteration num2 = carry; } return num1; }}Complexity
Time
O(k), where `k` is the number of bits. Similar to the recursive approach, the number of iterations depends on carry propagation. For fixed-size integers, this is O(1). It is generally faster than the recursive version due to the absence of function call overhead.
Space
O(1). The calculation is done in-place using a few variables, requiring constant extra space.
Trade-offs
Pros
More memory-efficient than the recursive approach (O(1) space).
Avoids potential stack overflow issues.
Clearly demonstrates knowledge of bitwise operations.
Cons
Still significantly more complex and slower than using the native
+operator.The logic can be non-obvious to those unfamiliar with bit manipulation.
Solutions
Solution
class Solution {public int sum(int num1, int num2) { return num1 + num2; }}class Solution: def sum(self, num1: int, num2: int) -> int: return num1 + num2class Solution {public: int sum(int num1, int num2) { return num1 + num2; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.