Lv.1arraycombinatoricsmath
Sum of All Subarray Sums
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given a non-negative integer array nums, add up the sums of all non-empty contiguous subarrays nums[l..r] and return
the total modulo .
Examples
| nums | result |
|---|---|
[1, 2, 3] | 20 |
[5] | 5 |
[1000000000, 1000000000] | 999999979 |
Example 1 — the subarray sums are 1, 2, 3, 3, 5, 6, totalling 20.
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
-
nums.length -
nums[i] - Return the answer modulo .
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| nums | Expected |
|---|---|
[1,2,3] | 20 |
[5] | 5 |
[1000000000,1000000000] | 999999979 |
Hint
Hint
Count how many subarrays contain nums[i]: i + 1 choices of start and n - i choices of end, so the answer is
. Reduce (up to about ) modulo before multiplying by nums[i]
so 64-bit arithmetic does not overflow. Extending a running sum from every start is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1022 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 10 | verdict only |
| performance | 60 | 3 | verdict only |