# Sum it Up

Source: https://www.techinterview.org/post/526329049/sum-it-up/
Updated: 2026-07-05 · techinterview.org

Problem: you are given a sequence of numbers from 1 to n-1 with one of the numbers repeating only once. (example: 1 2 3 3 4 5). how can you find the repeating number? what if i give you the constraint that you can’t use a dynamic amount of memory (i.e. the amount of memory you use can’t be related to n)?

what if there are two repeating numbers (and the same memory constraint?)

### Solution

as a programmer, my first answer to this problem would be make a bit vector of size n, and every time you see the number, set its correspond index bit to 1. if the bit is already set, then that’s the repeater. since there were no constraints in the question, this is an ok answer. its good because it makes sense if you draw it for someone, whether they are a programmer, mathemetician, or just your grandpa. its not the most efficient answer though.

now, if i add the constraint that you can only use a fixed amount of memory (i.e. not determined by n) and it must run in O(n) time… how do we solve it. adding all the numbers up from 1 to n-1 would give us a distinct sum. subtracting the total sum of all the numbers from the sum of n to n-1 ( which is (n)(n-1)/2 ) would give us the secret extra number.

what if you can only use a fixed amount of memory, and **two** of the numbers are repeated? we know that the numbers have a distinct sum, and the difference would be equal to the sum of our unknowns

`c = a + b`

where c is the sum and *a* and *b* are the unknowns - c is a constant

if we had another similar formula we could solve the two unknown equations. my first thought was that the numbers would have a distinct product - (n-1)!

if we divide the total product by the (n-1)! product, we would get another equation

`c2 = ab`

we could then solve the two equations to get them into quadratic formula notation

`0 = ax^2 + bx + c`

and solve for the two values of x. this answer is correct but factorial grows really fast.

some sort of sum would be better. the sum of the squares from n-1 to 1 would work. that would yield a function of the form

`c2 = a^2 + b^2`

which could also be solved by using the quadratic equation.

i think its fine to remind someone of the quadratic equation… (maybe only because i myself had to look it up to solve the problem) i mean really though, the last time i used it was probably in 10th grade. as long as they get the idea that given two unknowns and two equations you can solve for the unknowns - thats the point.

## 2026 Update: Subset Sum — NP-Complete but Practically Solvable

The subset sum problem: given a set of integers, does any subset sum to a target value T? This is NP-complete in general, but common interview constraints make it tractable.


```
from functools import lru_cache

# Approach 1: DP — O(n × T) time and space
def subset_sum_dp(nums: list, target: int) -> bool:
    n = len(nums)
    # dp[i][s] = can we make sum s using first i numbers?
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    dp[0][0] = True  # Empty subset sums to 0

    for i in range(1, n + 1):
        for s in range(target + 1):
            dp[i][s] = dp[i-1][s]  # Don't take num[i-1]
            if s >= nums[i-1]:
                dp[i][s] |= dp[i-1][s - nums[i-1]]  # Take num[i-1]

    return dp[n][target]

# Approach 2: Space-optimized DP — O(T) space
def subset_sum_1d(nums: list, target: int) -> bool:
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for s in range(target, num - 1, -1):  # Traverse backwards!
            dp[s] |= dp[s - num]
    return dp[target]

# Approach 3: Recursive + memoization
def subset_sum_memo(nums: list, target: int) -> bool:
    @lru_cache(maxsize=None)
    def dp(i, remaining):
        if remaining == 0: return True
        if i == len(nums) or remaining < 0: return False
        # Skip nums[i], or take it and reduce remaining
        return dp(i + 1, remaining) or dp(i + 1, remaining - nums[i])
    return dp(0, target)

# Two Sum — O(n) hash map, the classic (LeetCode #1)
def two_sum(nums: list, target: int) -> tuple:
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return (seen[complement], i)
        seen[num] = i
    return None

# Test cases
nums = [3, 34, 4, 12, 5, 2]
print(subset_sum_dp(nums, 9))     # True (4+5=9)
print(subset_sum_dp(nums, 30))    # False
print(two_sum([2,7,11,15], 9))    # (0, 1) — indices of 2 and 7
```

**Interview progression:**

- **Two Sum:** O(n) with hash map — LeetCode #1, asked at every company

- **3-Sum:** O(n²) sort + two pointers — LeetCode #15

- **Partition Equal Subset Sum:** Can array split into equal halves? — LeetCode #416

- **Target Sum:** Assign +/- to each number to hit target — LeetCode #494

The DP pattern (1D array, traverse backwards) is reusable for 0/1 knapsack and coin change. Interviewers often start with two sum and escalate to full subset sum to test DP knowledge.