1
2
3
4
[0][1][2][3]
Brute force
▸1given arr; output ← new array[n]2for i ← 0 to n − 1:3 p ← 14 for j ← 0 to n − 1 where j ≠ i: p ← p × arr[j]5 output[i] ← p6return output
state
- ruleno division
Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.
Try one problemGiven an integer array, return an array where output[i] equals the product of every element except arr[i]. Solve it in O(n) time without using the division operation.
▸1given arr; output ← new array[n]2for i ← 0 to n − 1:3 p ← 14 for j ← 0 to n − 1 where j ≠ i: p ← p × arr[j]5 output[i] ← p6return output
line 1For each i, output[i] is the product of EVERY other element. The obvious move — total product ÷ arr[i] — is banned (division), and it also blows up if any element is 0.