# Add Two Integers
**Difficulty:** EASY
[External](https://leetcode.com/problems/add-two-integers)
Canonical: https://scaleengineer.com/dsa/problems/add-two-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Jane Street](https://scaleengineer.com/companies/jane-street)
---
## Problem
Given two integers `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
## Recursive Bit Manipulation
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.
**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).
**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.
### Explanation
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.
```java
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);
    }
}
```
### Algorithm
- Define a recursive function `sum(a, b)`.
- If `b` is 0, it means there are no more carries to process. Return `a`.
- 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)`.

## Iterative Bit Manipulation
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.
**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.
**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.
### Explanation
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 `while` loop 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 original `num2` to calculate the new `num1`.
- Next, we update `num1` to be the sum of bits without carry: `num1 = num1 ^ num2`.
- Finally, we update `num2` to be the `carry` we calculated, preparing for the next iteration.
- Once the loop terminates (`num2` is 0), `num1` holds the complete sum.
```java
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;
    }
}
```
### Algorithm
- Initialize a loop that continues as long as `num2` is not 0.
- Inside the loop, compute the carry: `carry = (num1 & num2) << 1`.
- Update `num1` to the sum without carry: `num1 = num1 ^ num2`.
- Update `num2` to be the `carry`.
- After the loop, `num1` holds the final sum. Return `num1`.

## Direct Addition using `+` Operator
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    public int sum(int num1, int num2) {
        return num1 + num2;
    }
}
```
### Algorithm
- Add `num1` and `num2` using the `+` operator.
- Return the result.

# Solutions
### Java

```java
class Solution {
public
  int sum(int num1, int num2) { return num1 + num2; }
}

```

### Python

```python
class Solution:
    def sum(self, num1: int, num2: int) -> int: return num1 + num2

```

### CPP

```cpp
class Solution {
public:
  int sum(int num1, int num2) { return num1 + num2; }
};

```