Funcia
Lv.1arraymathprefix-sum

Sum of Pairwise Products

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

For every pair of distinct indices i < j of skill, the pair scores skill[i] × skill[j]. Return the sum of the scores of all pairs modulo 1,000,000,0071{,}000{,}000{,}007.

Examples

skillresult
[1, 2, 3]11
[4, 0, 5, 1]29
[1000000000, 1000000000]49

Example 1 — 1×2 + 1×3 + 2×3 = 11.

Efficiency

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

Function signature

solution(skill: int[]) → int

Constraints

  • 2≤2 \le skill.length ≤200,000\le 200{,}000
  • 0≤0 \le skill[i] ≤109\le 10^9
  • Return the answer modulo 1,000,000,0071{,}000{,}000{,}007.

Expected complexity

Time
O(N)
Space
O(1)

Examples

skillExpected
[1,2,3]11
[4,0,5,1]29
[1000000000,1000000000]49

Hint

Hint

Fixing j, its pairs with earlier members sum to (skill[0]+⋯+skill[j−1])×skill[j](\text{skill}[0] + \dots + \text{skill}[j-1]) \times \text{skill}[j]. Keep the running sum (mod 109+710^9+7) while sweeping left to right, and use 64-bit multiplication. Multiplying every pair 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 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

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

No result yet. Run or submit your code.