Sum it Up – Tech Interview Dot 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.

💡Strategies for Solving This Problem

Two Sum Variant

This is usually "find two numbers that sum to target." It's the most common interview question - I've gotten it or variants at Google, Facebook, and Amazon.

The Core Pattern

For each number, ask: "Have I seen (target - current) before?" If yes, found the pair. If no, remember current number.

This is the hash map pattern - you'll use it constantly.

Approach 1: Hash Map (Standard)

Single pass through array. O(n) time, O(n) space.

This is what 90% of interviewers expect. Know this cold.

Approach 2: Two Pointer (If Sorted)

If array is sorted (or you can sort it): two pointers from start and end. Move left if sum too small, move right if sum too large.

O(n log n) for sorting + O(n) for two pointers = O(n log n) time, O(1) space.

Approach 3: Brute Force (Don't Do This)

Check every pair with nested loops. O(n²) time. Only acceptable if you're completely blanking and need to start somewhere.

Common Follow-ups

"Return indices, not values" - slight variation
"Find all pairs, not just one" - same approach, don't return early
"What if array has duplicates?" - handle carefully
"Can you use less space?" - two pointer if sorting is allowed

✅Solution

Solution: Hash Map (One Pass)

function twoSum(nums, target) {
    const seen = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (seen.has(complement)) {
            return [seen.get(complement), i];
        }

        seen.set(nums[i], i);
    }

    return [];  // No solution found
}

// Tests
console.log(twoSum([2, 7, 11, 15], 9));    // [0, 1]
console.log(twoSum([3, 2, 4], 6));         // [1, 2]
console.log(twoSum([3, 3], 6));            // [0, 1]
console.log(twoSum([1, 2, 3], 10));        // []

Why This Works

For target=9, array=[2, 7, 11, 15]:

i=0, num=2: complement=7, not seen. Add 2→0 to map
i=1, num=7: complement=2, seen at index 0! Return [0,1]

We check for complement BEFORE adding current number. This handles the case where target = 2×number (can't use same element twice).

Alternative: Two Pointers (If Sorting Allowed)

function twoSumSorted(nums, target) {
    // If array isn't sorted, sort it first
    // Note: this loses original indices
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const sum = nums[left] + nums[right];

        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;  // Need larger sum
        } else {
            right--; // Need smaller sum
        }
    }

    return [];
}

// For sorted array
console.log(twoSumSorted([1, 2, 3, 4, 6], 6));  // Finds 2+4=6

Returning Values Instead of Indices

function twoSumValues(nums, target) {
    const seen = new Set();

    for (let num of nums) {
        const complement = target - num;

        if (seen.has(complement)) {
            return [complement, num];
        }

        seen.add(num);
    }

    return [];
}

console.log(twoSumValues([2, 7, 11, 15], 9));  // [2, 7]

Finding All Pairs

function twoSumAllPairs(nums, target) {
    const seen = new Map();
    const pairs = [];

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (seen.has(complement)) {
            pairs.push([seen.get(complement), i]);
        }

        seen.set(nums[i], i);
    }

    return pairs;
}

console.log(twoSumAllPairs([1, 2, 3, 4, 2], 5));
// [[1, 2], [0, 3]]  (indices where values sum to 5)

Complexity Analysis

Hash Map: O(n) time, O(n) space - best overall
Two Pointer: O(n log n) time (sorting), O(1) space - if space matters
Brute Force: O(n²) time, O(1) space - never use in interview

Edge Cases

No solution: Return empty array
Multiple solutions: Return first found (or all if asked)
Duplicates: [3,3] target 6 works (different indices)
Negative numbers: Algorithm works fine

Why this matters: Two Sum is the foundation for Three Sum, Four Sum, and many other problems. Master this pattern.