371. Sum of Two Integers

Sum of Two Integers (LeetCode 371) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise XOR - Finding Single/Missing Number subpattern.

How to solve Sum of Two Integers

Sum of Two Integers is a XOR for Single and Missing Numbers problem, part of Bit Manipulation Patterns. Use XOR properties to find single number, missing number, and duplicates.

Work towards the solution in these steps:

  1. At each binary position, separate the bits that contribute directly to the result from the bits that represent a carry.
  2. Bitwise XOR combines two bits without carrying, while bitwise AND identifies positions that generate carries.
  3. Shift the carry one position left and repeat until no carry remains.

The reference solution runs in O(w) time and O(1) space.

The Sum of Two Integers solution and editorial walks through the full approach with reference code.

Problem statement

Implement Solution.getSum(a, b) to compute the arithmetic sum of the two integer parameters a and b. Return that sum as a JSON integer.

The implementation must not use the + or - operators anywhere in the addition logic. Use bitwise operations to reproduce the effects of adding binary digits and propagating carries.

Both positive and negative values are valid, including zero. The returned value must be mathematically equal to a + b, even though the forbidden operators cannot be used.

Example 1:

Input: a = 14, b = -6 Output: 8 Explanation: Adding 14 and -6 produces 8. The method must obtain this result without using the forbidden arithmetic operators.

Example 2:

Input: a = -23, b = 7 Output: -16 Explanation: The negative value has greater magnitude, so the sum is -16.

Example 3:

Input: a = 0, b = 19 Output: 19 Explanation: Adding zero leaves the other integer unchanged.

Constraints:

- a is an integer. - b is an integer. - -1000 <= a <= 1000. - -1000 <= b <= 1000. - The + operator must not be used. - The - operator must not be used.

Topics and companies

Topics: Bit Manipulation, Math, Iteration.

How to practise Sum of Two Integers on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(w) time and O(1) space.

Open Sum of Two Integers in the code editor, or read the Sum of Two Integers editorial for a worked solution with its approach and complexity analysis.

Where Sum of Two Integers sits in the DSA pattern sheet

Problems related to Sum of Two Integers

Other problems that use the same Bitwise XOR - Finding Single/Missing Number and Bit Manipulation Patterns techniques:

Sum of Two Integers FAQ

What is the LeetCode number of Sum of Two Integers?

Sum of Two Integers is LeetCode problem 371, rated Medium.

What pattern is used to solve Sum of Two Integers?

Sum of Two Integers is a XOR for Single and Missing Numbers problem. It belongs to the Bit Manipulation Patterns pattern, in the Bitwise XOR - Finding Single/Missing Number subpattern.

What is the time complexity of Sum of Two Integers?

The reference solution runs in O(w) time and O(1) space.

Preparing this workspace.