Funcia
Lv.1arraymathprefix-sum

Product Except Self

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an integer array nums, return an array whose i-th value is the product of every element except nums[i], modulo 1,000,000,0071{,}000{,}000{,}007. nums may contain 0.

Examples

numsresult
[1, 2, 3, 4][24, 12, 8, 6]
[3, 0, 5][0, 15, 0]
[1000000000, 1000000000][1000000000, 1000000000]

Example 2 — only position 1 skips the 0, giving 3×5 = 15.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(nums: int[]) → int[]

Constraints

  • 2≤2 \le nums.length ≤200,000\le 200{,}000
  • 0≤0 \le nums[i] ≤109\le 10^9
  • Every returned value is taken modulo 1,000,000,0071{,}000{,}000{,}007.

Expected complexity

Time
O(N)
Space
O(N)

Examples

numsExpected
[1,2,3,4][24,12,8,6]
[3,0,5][0,15,0]
[1000000000,1000000000][1000000000,1000000000]

Hint

Hint

The product without i is (product of everything left of i) × (product of everything right of i). Build both with one pass each, taking the modulus after every multiplication (use 64-bit arithmetic). Dividing the total product by nums[i] fails with zeros and does not work under a modulus. Multiplying the others for each position is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251356 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.