Power-Up Multipliers
In a card game you are building, each player holds a row of power-up cards. Every card has a multiplier: 3 triples your score, -1 flips it negative, 0 wipes it out. Your score multiplier is all the cards multiplied together.
Before each turn the game must discard one card, and it shows, under every card, what the multiplier would be if that card were the one discarded. The game's scoring code only multiplies: dividing the full product by a card breaks as soon as a card is 0.
Your task
Write withoutEach(cards). Return a list out of the same length where out[i] is the product of every card except cards[i].
Do not use division. Aim for O(n) time.
withoutEach(cards: int[]) → int[]
Examples
cards = [2, 3, 4, 5]
[60, 40, 30, 24]
Without the 2: 3 × 4 × 5 = 60. Without the 3: 2 × 4 × 5 = 40. Without the 4: 2 × 3 × 5 = 30. Without the 5: 2 × 3 × 4 = 24.
cards = [3, 0, 2, -1]
[0, -6, 0, 0]
Every product that keeps the 0 is 0. Only discarding the 0 itself gives something else: 3 × 2 × (-1) = -6. Dividing the full product (0) by 0 would crash here.
Constraints
- 2 ≤ cards.length ≤ 100,000
- -20 ≤ cards[i] ≤ 20
- The product of all the non-zero cards fits in a 32-bit signed integer.
Start with brute force
For each position, loop over all the other cards and multiply them together.
That is n − 1 multiplications for each of n positions, so O(n²). With 100,000 cards it is about 10 billion multiplications. Neighbouring answers share almost all their factors, and the brute force recomputes them every time. The division shortcut is O(n) but fails on zeros.
Hints
0 of 4 shown- Hint 1
In
[2, 3, 4, 5], the answer under the 4 is 2 × 3 × 5. Which of those cards sit to the left of the 4, and which to the right? - Hint 2
Every answer is (product of all cards to the left) × (product of all cards to the right). For the first card, the left side is empty and counts as 1.
- Hint 3
The products of everything to the left of each position can be built in one pass from left to right, each from the previous one. The right-hand products work the same way from the other end.
- Hint 4
Fill
out[i]with the product of everything beforei, using a running product that starts at 1. Then walk from the right with a second running product, starting at 1: multiplyout[i]by it, then multiply it bycards[i].
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Removing card i splits the row in two: the cards before it and the cards after it. The answer is the product of the first part times the product of the second. Both parts can be built up one card at a time, the same way a running sum is.
Trace [2, 3, 4, 5].
- Left pass, writing the product of everything before each card:
out = [1, 2, 6, 24]. (1 for nothing, then 2, then 2 × 3, then 2 × 3 × 4.) - Right pass, starting with
right = 1. Index 3: out[3] = 24 × 1 = 24, then right = 5. - Index 2: out[2] = 6 × 5 = 30, then right = 20.
- Index 1: out[1] = 2 × 20 = 40, then right = 60.
- Index 0: out[0] = 1 × 60 = 60. Result:
[60, 40, 30, 24].
In each pass, write the answer before multiplying in the current card. That is what keeps card i out of its own answer. Zeros need no special case: they simply turn the running product to 0 for everything past them.
function withoutEach(cards) {
const n = cards.length;
const out = new Array(n);
let left = 1; // product of cards before i
for (let i = 0; i < n; i++) {
out[i] = left;
left *= cards[i];
}
let right = 1; // product of cards after i
for (let i = n - 1; i >= 0; i--) {
out[i] *= right;
right *= cards[i];
}
return out;
}def without_each(cards):
n = len(cards)
out = [1] * n
left = 1 # product of cards before i
for i in range(n):
out[i] = left
left *= cards[i]
right = 1 # product of cards after i
for i in range(n - 1, -1, -1):
out[i] *= right
right *= cards[i]
return outRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.