Loading page…
Practice problem · medium
A bank app gives each account a risk score. To judge an account fairly, an analyst wants the product of the scores of all the other accounts, which shows how risky the rest of the portfolio is.
The product can be huge, so every answer is reported as a remainder modulo 1,000,000,007. Some accounts have a score of 0, and your code must not divide.
Write product_of_others(values).
values[i] is the risk score of the i-th account.values[j] with j != i, modulo 1,000,000,007.Input: values = [1, 2, 3, 4]
Output: [24, 12, 8, 6]The trace multiplies from the left to get the product of everything before each position, then from the right to get everything after it.
| Position | Product before | Product after | Answer |
|---|---|---|---|
| 0 | 1 (nothing) | 2 × 3 × 4 = 24 | 24 |
| 1 | 1 | 3 × 4 = 12 | 12 |
| 2 | 1 × 2 = 2 | 4 | 8 |
| 3 | 1 × 2 × 3 = 6 | 1 (nothing) | 6 |
The values are 1, 2, 3, 4. The output is [24, 12, 8, 6].
Input: values = [5]
Output: [1]For one account, the product of the others is the empty product, 1.
Input: values = [2, 0, 3]
Output: [0, 6, 0]Position 0 is the product of 0 and 3, which is 0. Position 1 is 2 × 3 = 6. Position 2 is 2 × 0 = 0, so the output is [0, 6, 0].
1 ≤ values.length ≤ 100,000 (accounts)0 ≤ values[i] ≤ 1,000,000 (risk scores)Multiplying all the others for each position costs n × n steps, about 10^10 at n = 100,000. Prefix and suffix products take two passes of n steps. Division fails when a score is 0, and with a modulus it needs an inverse, so the task rules it out. Before each modulus a product is at most about 10^9 × 10^9 = 10^18, a stored part times a running part, so it fits in 64 bits.
product_of_others · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.