Product except self

Why this matters

A common array question asks for a new array where each box holds the product of all the other boxes. The question looks simple, and most people solve it first with division. This lesson shows why division is the wrong tool here, and how two passes over the array solve the problem with plain multiplication.

The method is a close cousin of prefix sums, which the earlier lesson on prefix sums and two pointers covers. A prefix sum adds up everything before a point. Here we multiply instead of adding, and we do the work from both ends of the array.

The problem in plain words

You have an array of numbers. Call it nums. Its boxes are numbered from 0. You want a second array, result, the same length. For each box i, result[i] must be the product of every value in nums except nums[i].

A product is what you get when you multiply values together. The product of 2, 3 and 4 is 2 times 3 times 4, which is 24.

Here is a small example.

nums:    1  2  3  4
result: 24 12  8  6

Check box 0. The other values are 2, 3 and 4. Their product is 24. Check box 2. The other values are 1, 2 and 4. Their product is 8. Every box follows the same rule.

Two rules for the problem:

• You must not use the value nums[i] when you build result[i].
• You should not use division. The next section explains why.

Why not divide

The first idea most people try is to multiply all the values together once, then divide that total by each value. For 1 2 3 4 the total is 24. Then 24 divided by 1 is 24, 24 divided by 2 is 12, and so on. That gives the right answer.

The idea breaks when a value is zero. Dividing by zero has no answer, and in C++ integer division by zero is undefined behaviour. That phrase means the language does not say what happens, so the program can do anything. In practice, the program usually crashes.

Here is a short program that divides by a zero value.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{2, 0, 5};
    int total = 1;
    for (int v : nums) {
        total *= v;
    }
    std::cout << "total = " << total << "\n";
    for (std::size_t i = 0; i < nums.size(); ++i) {
        std::cout << total / nums[i] << "\n";
    }
}

Compile and run it on Linux with GCC 15.2.

$ g++ -std=c++20 -Wall -o div div.cpp
$ ./div
total = 0
0
$ echo $?
136

The program stopped with exit code 136. An exit code is the number a program returns when it ends. The number 136 means the program was stopped by signal 8, which is the floating point exception signal. On a terminal the two lines appear. When the output goes to a file or a pipe, they are lost, because they are still waiting in a buffer when the program crashes. A buffer is a short holding area where text waits before it is written out. A crash can throw away what is in the buffer.

The division method also needs extra work to handle zeros. You would have to count the zeros and treat each case by hand. The two-pass method below needs no division, so zeros need no special care.

The idea: what is on the left, what is on the right

Pick any box i. The answer for box i is made of two parts.

• The left part is the product of all values in boxes 0 up to i - 1. This is everything to the left of i.
• The right part is the product of all values in boxes i + 1 up to the end. This is everything to the right of i.

The answer is the left part times the right part. The value in box i itself is left out, because it is not in either part.

Take 2 3 4 5 and look at each box.

index  value  left part   right part   answer
  0      2     1          3*4*5 = 60     60
  1      3     2          4*5 = 20       40
  2      4     2*3 = 6    5              30
  3      5     2*3*4 = 24 1              24

The left part for box 0 is an empty product. Nothing is to its left, and an empty product is 1, because multiplying by 1 changes nothing. The same holds for the right part of the last box. Start every running product at 1, not at 0. If you start at 0, every product stays 0 and every answer is wrong.

This gives a plan with two passes.

1. Walk from left to right. Keep a running product of the values seen so far. Before you multiply in a value, store the running product as that box's left part.
2. Walk from right to left. Keep a second running product of the values seen from the right. Multiply each box by that running product, which gives its right part. Then multiply the running product by the value in the box.

First version: two helper arrays

The clearest version uses two extra arrays. One holds the left parts, called prefix. The other holds the right parts, called suffix. At the end you multiply the two arrays box by box.

#include <iostream>
#include <vector>
 
// Version 1: two helper arrays, one prefix pass and one suffix pass.
std::vector<int> productExceptSelf(const std::vector<int>& nums) {
    const std::size_t n = nums.size();
    std::vector<int> prefix(n, 1);
    std::vector<int> suffix(n, 1);
 
    for (std::size_t i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] * nums[i - 1];
    }
    for (std::size_t i = n - 1; i-- > 0;) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }
 
    std::vector<int> result(n);
    for (std::size_t i = 0; i < n; ++i) {
        result[i] = prefix[i] * suffix[i];
    }
    return result;
}
 
int main() {
    std::vector<int> nums{2, 3, 4, 5};
    for (int v : productExceptSelf(nums)) {
        std::cout << v << " ";
    }
    std::cout << "\n";
}

Here is the output of that program.

60 40 30 24

Read the code in order. prefix[i] is built from prefix[i - 1], which means the left part of box i is the left part of box i - 1 times the value just before i. The loop for suffix runs backwards, so suffix[i] is built from suffix[i + 1]. The final loop multiplies the two arrays.

The loop header for (std::size_t i = n - 1; i-- > 0;) is a way to count down from n - 1 to 0 with an unsigned type. The test i-- > 0 checks the old value of i and then lowers it. Each time through, i takes the values n - 2, n - 3 and so on down to 0. This version does not handle an empty input. The mistakes section shows what goes wrong.

Second version: one output array

The first version uses three arrays. The second version uses only the output array and one running variable. The result is the same, and the code is shorter to read once you know the pattern.

The trick is that the output array can hold the left parts first. The first pass stores each left part in its box. The second pass then multiplies each box by its right part, which turns the left part into the full answer.

#include <iostream>
#include <vector>
 
// Version 2: one output array, running products instead of helper arrays.
std::vector<long long> productExceptSelf(const std::vector<int>& nums) {
    const std::size_t n = nums.size();
    std::vector<long long> result(n, 1);
 
    long long running = 1;
    for (std::size_t i = 0; i < n; ++i) {
        result[i] = running;
        running *= nums[i];
    }
 
    running = 1;
    for (std::size_t i = n; i > 0; --i) {
        result[i - 1] *= running;
        running *= nums[i - 1];
    }
    return result;
}
 
void show(const std::vector<int>& nums) {
    std::cout << "input:  ";
    for (int v : nums) std::cout << v << " ";
    std::cout << "\noutput: ";
    for (long long v : productExceptSelf(nums)) std::cout << v << " ";
    std::cout << "\n\n";
}
 
int main() {
    show({1, 2, 3, 4});
    show({-1, 1, 0, -3, 3});
    show({0, 0, 7});
    show({5});
    show({});
}

The result is long long, which holds much larger numbers than int. The next section explains why that matters. The running variable is also long long.

Here is the output.

input:  1 2 3 4 
output: 24 12 8 6 
 
input:  -1 1 0 -3 3 
output: 0 0 9 0 0 
 
input:  0 0 7 
output: 0 0 0 
 
input:  5 
output: 1 
 
input:  
output: 

The last two cases show two rules. A single value has nothing else to multiply, so its answer is the empty product, 1. An empty input gives an empty output.

Worked examples

Example 1: all positive values

Use 1 2 3 4 and version 2. Before the first pass, running is 1. The first pass writes the left parts and multiplies running as it goes.

i   nums[i]   result[i] = running before multiply   running after multiply
0      1       1                                        1
1      2       1                                        2
2      3       2                                        6
3      4       6                                        24

After the first pass result is 1 1 2 6. These are the left parts. Now the second pass starts with running at 1 and walks from the right.

i   nums[i]   result[i] *= running   running after multiply
3      4       6 * 1 = 6               4
2      3       2 * 4 = 8               12
1      2       1 * 12 = 12             24
0      1       1 * 24 = 24             24

The final result is 24 12 8 6. Each box has the product of everything except itself.

Example 2: negative values and a zero

Now use -1 1 0 -3 3. The rule is the same, but the zero changes the outcome for every box except one.

Box 2 holds the zero. Its left part is -1 * 1 = -1. Its right part is -3 * 3 = -9. The answer is -1 * -9 = 9. The zero is left out, so the product of the other values is 9.

Every other box has the zero in one of its parts. That makes the product 0. So the output is 0 0 9 0 0.

A rule follows from this. If the input has one zero, only the box that holds the zero gets a non-zero answer. If it has two or more zeros, every answer is 0. The two-pass method gets this right with no special code. A division method would need to find and count the zeros first.

Example 3: a longer input and the size of the numbers

Try 1 2 3 ... 13. Each answer is the product of 12 numbers. The product of 1 to 13 is 6227020800. That number is bigger than the largest int on common systems, which is 2147483647.

Here is a program that multiplies the same numbers into an int and into a long long.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
    int running = 1;
    for (int v : nums) {
        running *= v;
    }
    std::cout << "product of 1..13 as int: " << running << "\n";
    long long wide = 1;
    for (int v : nums) {
        wide *= v;
    }
    std::cout << "product of 1..13 as long long: " << wide << "\n";
}

The output on this machine was the following.

product of 1..13 as int: 1932053504
product of 1..13 as long long: 6227020800

The int result is wrong. When a signed int goes past its largest value, C++ calls it undefined behaviour, so the value you see is not a reliable answer. The long long result is correct.

When you solve this problem, read the limits in the task. If the task says the values are small and the array is short, int may be enough. If the task does not say, use long long for the output and running products.

Why it runs in linear time

Linear time means the work grows in step with the input. Doubling the number of values roughly doubles the work. This is written O(n), where n is the number of values. The time and space complexity lesson explains the notation in full.

The two-pass method does a fixed amount of work for each box. Version 2 has two loops, each of length n. Each step does one comparison and one store, plus one or two multiplies. Counting the multiplies, the first loop does n and the second loop does 2n, so the total is 3n. That is still linear.

The extra memory is small. Version 2 writes into the output array, which the task asks for anyway. It adds one running variable. That takes the same amount of space no matter how long the input is.

Common mistakes

Dividing by zero

Using total / nums[i] is wrong when nums[i] is 0. On this machine the program in the division section stopped with exit code 136. Some other programs fail with a different message, or with no message at all. Avoid division for this problem.

Starting the running product at 0

If running starts at 0, every product multiplies by 0 and every answer is 0. The running product must start at 1, the empty product. The mistake is easy to make because 0 is a common starting value for sums. For products, the start value is 1.

Walking off the end on an empty input

Version 1 has a loop that starts at n - 1. When n is 0, n - 1 is not -1. The type is std::size_t, which is unsigned, so 0 - 1 wraps around to a very large number. The loop then reads boxes that do not exist.

Here is a program that calls version 1 with an empty input. It is compiled with GCC's checking option, which is -D_GLIBCXX_ASSERTIONS. The option turns on checks in the standard library.

#include <iostream>
#include <vector>
 
// Version 1 with the loop that goes from n - 1 down, but input is empty.
std::vector<int> productExceptSelf(const std::vector<int>& nums) {
    const std::size_t n = nums.size();
    std::vector<int> suffix(n, 1);
    for (std::size_t i = n - 1; i-- > 0;) {
        suffix[i] = suffix[i + 1] * nums[i + 1];
    }
    return suffix;
}
 
int main() {
    std::cout << productExceptSelf({}).size() << "\n";
}

The error message from the run was the following.

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The message says that an index was used while it was outside the vector. The fix is to return early when n is 0, or to write the loop so it never starts at n - 1. Version 2 avoids the problem because its loops run from 0 up, or from n down to 1.

Using int for large products

The int mistake was shown in example 3. The wrong answer came with no warning from the compiler. Check the limits in the task, and use long long when the products may be large.

Comparing a signed int with the size

A loop like the following compiles, but the compiler warns about it.

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> nums{1, 2, 3};
    for (int i = 0; i < nums.size(); ++i) {
        std::cout << nums[i] << "\n";
    }
}

With -Wall, GCC 15.2 reports this warning.

sgn.cpp: In function ‘int main()’:
sgn.cpp:6:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    6 |     for (int i = 0; i < nums.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

The warning says that int is signed and size() returns an unsigned type. The comparison can give wrong results for negative values. Use std::size_t for indexes, as the code in this lesson does.

Practice

Exercise 1

Work out the answer by hand for 1 5 2 and check your result against the code.

Show the answer

Box 0: the other values are 5 and 2, and 5 times 2 is 10. Box 1: the other values are 1 and 2, and 1 times 2 is 2. Box 2: the other values are 1 and 5, and 1 times 5 is 5. The answer is 10 2 5.

Exercise 2

For the input 3 0 4, what is the output? Explain each box in one sentence.

Show the answer

The output is 0 12 0. Box 0 holds 3, and its other values are 0 and 4, so the product contains 0 and is 0. Box 1 holds 0, and its other values are 3 and 4, which multiply to 12. Box 2 holds 4, and its other values are 3 and 0, so the product contains 0 and is 0.

Exercise 3

Change version 2 so that it returns std::vector<int> instead of std::vector<long long>, but keeps the running product as long long. Then say what each answer on the input 1000 1000 1000 1000 is, and whether it fits in an int.

Show the answer

Change the return type and the type of result to std::vector<int>, and convert when you store each value. Each answer is the product of three 1000s, which is 1000000000 (10 to the power 9). That is less than 2147483647, the largest int, so every answer fits. The running product reaches 1000000000000 (10 to the power 12) at the end of the first pass, which would overflow an int. That is why the running product stays long long.

Exercise 4

Why can one left-to-right pass not produce the answers? Give an example.

Show the answer

A left-to-right pass knows only the values before each box. For 1 2 3 4, box 0 needs 2 * 3 * 4, and the values 2, 3 and 4 come after it. When the pass reaches box 0, it has not seen them yet. The second pass from the right supplies the values that come after each box, so the two passes together cover both sides.

Exercise 5

Count the multiplications in version 1 for an input of length n. Give the total as a formula.

Show the answer

The prefix pass multiplies once for each box from 1 to n - 1, which is n - 1 multiplications. The suffix pass also multiplies once for each box except the last, which is n - 1 multiplications. The final pass multiplies each box once, which is n multiplications. The total is (n - 1) + (n - 1) + n, which is 3n - 2. The count is linear in n, the same as version 2.

Summary

• The answer for each box is the product of everything to its left times the product of everything to its right.
• A running product starts at 1, the empty product, not at 0.
• Two passes give the answer: one from left to right for the left parts, one from right to left for the right parts.
• Division is unsafe here, because a zero in the input makes the division undefined.
• Use long long when products may be larger than an int can hold.
• Keep indexes as std::size_t and guard against an empty input, because 0 - 1 on an unsigned type wraps around.