MySmartCoPilot
Ask Passes Your pass 7 days left 1 day left Last day

Your country

Tools that support it use your country for local currency, number formats, units and paper size. Your choice is saved only in this browser.

Coding Interview Patterns  Module 3 – Arrays and hashing

Product of all others: prefix and suffix passes

Compute the product of every element except the one at each position without division, with one prefix pass and one suffix pass, then max and gcd.

  • Beginner
  • 20 minutes
  • Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0, quickjs 0.32.0 and Java temurin-25.0.4+101.0.LTS
  • By MySmartCoPilot
Free: The problem: the score of removing each tile. With a pass: the other 10 sections and 3 interview answers, about 15 minutes.

What you will learn

  • Compute everything-except-one answers with a prefix pass and a suffix pass
  • Explain why dividing the total fails when the values include zero
  • Limit the extra memory to O(1) beyond the output array
  • Apply the passes to maximum, gcd and bitwise OR, where division does not exist
  • Compute products exactly in each language, and spot where 64-bit integers wrap or JavaScript numbers round

Before you start

What you’ll learn · Before you start

What you will learn

  • Compute everything-except-one answers with a prefix pass and a suffix pass
  • Explain why dividing the total fails when the values include zero
  • Limit the extra memory to O(1) beyond the output array
  • Apply the passes to maximum, gcd and bitwise OR, where division does not exist
  • Compute products exactly in each language, and spot where 64-bit integers wrap or JavaScript numbers round

Before you start

On this page

Removing one tile from the row [2, 3, −1, 4] scores the product of the other three, so the four scores are [−12, −8, 24, −6]. Answers of this “everything except me” kind come from two passes: a pass from the left records what lies before each position, a pass from the right records what lies after it, and the answer at each position combines the two. No division is needed, so zeros cause no trouble, and the same passes work for the maximum, the greatest common divisor and other operations that cannot be undone at all. Its best-known form is the problem called product of array except self; an original version with tiles comes first, with its limits and the reason why multiplying everything again for each position is too slow.

The problem: the score of removing each tile

The problem

A puzzle game shows a row of n tiles, each with a whole-number multiplier from −9 to 9, zero included. Removing a tile scores the product of the multipliers of all the other tiles. Return the score that removing each tile would give. Limits: 2 ≤ n ≤ 100,000, and the product of the tiles before any position, and of those after it, fits in a signed 64-bit integer.

  1. [2, 3, −1, 4] gives [−12, −8, 24, −6]: removing the −1 leaves 2 × 3 × 4 = 24.
  2. [5, 0, 2] gives [0, 10, 0]: only removing the zero leaves a product without it.
  3. [0, 7, 0] gives [0, 0, 0]: every product still contains a zero.
In the row 2, 3, −1, 4, the answer for position 2 is the product 6 of the tiles left of it times the product 4 of those right of it.The row: 2, 3, −1, 4Answer for position 2:6 × 4 = 2423−1(left out)4Left of position 2:2 × 3 = 6Right of position 2:4

The answer for one position, split in two

Text description of the diagram

The row has four tiles: 2, 3, −1 and 4. Position 2, the tile −1, is left out.

  • Left of position 2 are the tiles 2 and 3, whose product is 6.
  • Right of position 2 is the tile 4, whose product is 4.
  • The answer for position 2 is 6 × 4 = 24, the product of every tile except −1.

The brute force: multiply all the others

For each tile, multiply the multipliers of every other tile. It is plainly correct, so it is the reference for tests, but each of the n answers costs n − 1 multiplications:

Multiplying all the others for every tile Python · brute/others_brute.py 
"""The score of removing each tile: the product of all the other multipliers, by brute force."""


def scores_brute(tiles):
    """Returns (scores, multiplications): for each tile, multiply every other tile."""
    scores = []
    multiplications = 0
    for i in range(len(tiles)):
        product = 1
        for j, m in enumerate(tiles):
            if j != i:
                product *= m
                multiplications += 1
        scores.append(product)
    return scores, multiplications


print(scores_brute([2, 3, -1, 4])[0])
print(scores_brute([5, 0, 2])[0])
print(scores_brute([0, 7, 0])[0])

# n tiles cost n - 1 multiplications each, whatever the multipliers are.
for n in (1_000, 2_000):
    print(f"n = {n:,}: {scores_brute([1] * n)[1]:,} multiplications")
n = 100_000
print(f"n = {n:,}: {n * (n - 1):,} multiplications")

Output

[-12, -8, 24, -6]
[0, 10, 0]
[0, 0, 0]
n = 1,000: 999,000 multiplications
n = 2,000: 3,998,000 multiplications
n = 100,000: 9,999,900,000 multiplications

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 others_brute.py

That is n(n − 1) multiplications: about 10¹⁰ for 100,000 tiles, minutes of work where about a second is allowed. Step through the first example and watch the same multiplications come back for every tile:

Interactive · step by step Multiplying all the others for each tile of [2, 3, −1, 4] Step through the four answers. Each one multiplies the other three tiles from scratch; the narration keeps the count.
Multiplying all the others for each tile of [2, 3, −1, 4], step 6 of 6. Showing tile 0: 2, tile 1: 3, tile 2: −1, tile 3: 4, answer 0 (3 × −1 × 4 = −12), answer 1 (2 × −1 × 4 = −8), answer 2 (2 × 3 × 4 = 24), answer 3 (2 × 3 × −1 = −6). In focus: answer 0, answer 1, answer 2, answer 3.tile 0: 2tile 1: 3tile 2: −1tile 3: 4answer 03 × −1 × 4 = −12answer 12 × −1 × 4 = −8answer 22 × 3 × 4 = 24answer 32 × 3 × −1 = −6

The drawing shows the whole scene; its 6 steps are listed below.

Every step as text
  1. Four tiles, four answers. The row is 2, 3, −1 and 4. Removing a tile scores the product of the other three, so the brute force multiplies them again for every tile.
  2. Removing tile 0. Tile 0 is left out. Starting from 1, the product takes three multiplications: 3 × −1 × 4 = −12. 3 multiplications so far.
  3. Removing tile 1. Tile 1 is left out: 2 × −1 × 4 = −8. The −1 and the 4 are multiplied again, exactly as for tile 0. 6 multiplications so far.
  4. Removing tile 2. Tile 2 is left out: 2 × 3 × 4 = 24. 9 multiplications so far.
  5. Removing tile 3. Tile 3 is left out: 2 × 3 × −1 = −6. The answers are [−12, −8, 24, −6], after 12 multiplications.
  6. Why it is slow. Each answer cost n − 1 = 3 multiplications, so the row cost n(n − 1) = 12. For 100,000 tiles that is about 10¹⁰ multiplications, minutes of work where about a second is allowed.

What to notice

Every answer splits into the product of the tiles to the left of its position and the product of the tiles to the right, as the figure above shows for position 2. Neighbouring positions share almost all of that work, so building the parts once, in order, is enough. Three approaches are in common use:

  • Dividing the total product by each tile takes one line, but it divides by zero on the second example.
  • prefix product: The product of the elements before a position of a list, kept for every position and built in one pass from the left. A suffix product is the same from the right end. give each answer as the product of everything to its left times everything to its right.
  • One output array and one running product bring the extra memory down to O(1) beyond the output.

Checkpoint

Check: The score of removing each tile · Multiplying all the others, and its cost · Every answer splits into left and right

  1. Question 1 of 3 In the row [2, 3, −1, 4], what score does removing the 3 give?

    Choose one answer.

    Show the answer

    Answer: −8

    A tile's score is the product of every other tile: 2 × −1 × 4 = −8 for the 3, as the second answer of [−12, −8, 24, −6] says.

  2. Question 2 of 3 How many multiplications does the brute force make for a row of 1,000 tiles?

    Type a number.

    A hint

    Each tile's answer multiplies every other tile once.

    Show the answer

    Answer: 999000 multiplications

    Each of the 1,000 answers multiplies the other 999 tiles, so 1,000 × 999 = 999,000, the number the program printed. That is n(n − 1), which grows with the square of n.

  3. Question 3 of 3 Split the answer for position 1 of [2, 3, −1, 4] into its two parts. Which is right?

    Choose one answer.

    Show the answer

    Answer: Left of it: 2. Right of it: −1 × 4 = −4. The answer is 2 × −4 = −8.

    The answer for a position is the product of the tiles to its left times the product of the tiles to its right: 2 × (−1 × 4) = −8 for position 1.

The practice below covers the problem, its brute force and the split, and starts with whichever of them your answers show you know least.

Practice that adapts to you

Practise this lesson

9 questions about 10 ideas of this lesson. Each answer is explained at once, and what you get right is kept in this browser.

  1. Question 1 of 9 The row is [5, 0, 2]. Which scores are 0?

    Choose one answer.

    Show the answer

    Answer: The scores of removing the 5 and of removing the 2

    [5, 0, 2] gives [0, 10, 0]: only removing the zero leaves a product without it.

  2. Question 2 of 9 A row holds two zeros, such as [0, 7, 0]. What are the scores?

    Choose one answer.

    Show the answer

    Answer: Every score is 0

    With two zeros, every product of the others still holds a zero, so [0, 7, 0] gives [0, 0, 0]. With exactly one zero, only the zero's own score leaves it out.

  3. Question 3 of 9 A row of 100,000 tiles holds exactly one zero, at position k, and no other tile is 0. Which scores can be different from 0?

    Choose one answer.

    Show the answer

    Answer: Only the score of position k

    A score is 0 exactly when its product still holds a zero. With one zero, only removing that zero leaves a product without one, as [5, 0, 2] → [0, 10, 0] shows.

  4. Question 4 of 9 How many multiplications does the brute force make for one tile of a row of n tiles?

    Choose one answer.

    Show the answer

    Answer: n − 1

    Each answer multiplies the other n − 1 tiles, so the whole row costs n(n − 1) multiplications.

  5. Question 5 of 9 The brute force makes 999,000 multiplications for 1,000 tiles. How many does it make for 2,000 tiles?

    Type a number.

    A hint

    n(n − 1) with n = 2,000.

    Show the answer

    Answer: 3998000 multiplications

    2,000 × 1,999 = 3,998,000, the number the program printed: doubling the row makes about four times the work.

  6. Question 6 of 9 At 100,000 tiles the brute force needs about 10¹⁰ multiplications. With about 10⁷ simple steps a second in CPython, what does that mean?

    Choose one answer.

    Show the answer

    Answer: About 1,000 seconds, minutes of work where about a second is allowed

    The brute force cannot meet a one-second limit at these sizes, so the problem needs a method that does a few multiplications per tile.

  7. Question 7 of 9 What does every answer of the problem split into?

    Choose one answer.

    Show the answer

    Answer: The product of the tiles to the left of its position times the product of the tiles to its right

    For position 2 of [2, 3, −1, 4], the left part is 2 × 3 = 6 and the right part is 4, so the answer is 24, as the figure shows.

  8. Question 8 of 9 Which of the three ways in common use stops with an error on the row [5, 0, 2]?

    Choose one answer.

    Show the answer

    Answer: Dividing the total product by each tile

    Division takes one line but needs every tile to be non-zero; the other two ways never divide.

  9. Question 9 of 9 Which change to the problem would make dividing the total a correct one-line answer?

    Choose one answer.

    Show the answer

    Answer: No multiplier is 0

    Only a zero breaks the one-line division. The limits allow zeros, so the general method must not divide.

Two passes, step by step, with the invariant Pro

In this part:

  • A dry run on [2, 3, −1, 4]
  • One array and one running product: O(1) extra memory
  • Both passes in 14 languages
  • Why dividing the total fails, reproduced
  • Keeping products exact in each language
  • Any associative operation works: maximum, gcd and OR
  • Variants, edge cases and the common bugs
    • Variants
    • Edge cases and common bugs
  • Practice: the gcd of all the other values
    • The gcd of all the other values
  • Interview questions
    • Each answer must now be the product of all the other values modulo p = 10⁹ + 7, with values up to 10¹⁸. A colleague computes the total once and multiplies it by the modular inverse of each value. When does that give a wrong answer or crash, and what would you do instead?
    • A row has 10⁵ tiles, and 10⁵ operations arrive: each either changes one tile's multiplier or asks for the product of all the other tiles of one position, modulo 10⁹ + 7. What structure answers both kinds quickly, and what does each operation cost?
    • For each day of a temperature log of 10⁷ readings, report the highest reading on any other day. Can you do it with O(1) extra memory beyond the output, in one pass over the log and one pass to write the answers?
  • Key takeaways

2 diagrams · 6 runnable examples (Java, JavaScript, Python) · 1 exercise with sample tests · 3 interview answers · about 39 minutes

Opening this part with your pass…

This part opens with any MySmartCoPilot pass.

  • Pro pass · 1 week₹79$2.99
  • 30 days₹179$5.99
  • 1 year₹1,699$45

One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.

Choose a passI have a licence key

It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).

Terms in this lesson

associative operation
An operation for which the grouping does not change the result: (a ∘ b) ∘ c = a ∘ (b ∘ c). Addition, multiplication, maximum, gcd and bitwise OR are associative; taking an average is not.
identity element
A value that leaves every other value unchanged under an operation: 0 for addition, 1 for multiplication, minus infinity for the maximum and 0 for the greatest common divisor.
prefix product
The product of the elements before a position of a list, kept for every position and built in one pass from the left. A suffix product is the same from the right end.

References

Related tools

Python Online Compiler Real CPython in your browser — with stdin, files and a stop button. LCM & HCF (GCD) Calculator HCF and LCM with the working shown three ways — prime factors, ladder and Euclid. Big Number Calculator Every digit exact: huge sums, products, powers, roots and factorials.

Report a problem with this lesson