Sum of All Subarray Sums
Medium About 15 min Free, no account needed
Add up the sum of every contiguous subarray - without enumerating them.
The brief
Given an integer array nums, return the total of the sums of every
contiguous subarray.
For [1, 2, 3] the subarrays are [1] [2] [3] [1,2] [2,3] [1,2,3] with sums
1 + 2 + 3 + 3 + 5 + 6 = 20.
There are n(n+1)/2 subarrays; the obvious approach walks each one, O(n2). The hidden test uses 50,000 elements: 1.25 billion subarrays, so it's too slow. You need a single O(n) pass, which means finding the total without enumerating the subarrays at all.
Starter code
using System;
public class Solution
{
// TODO: return the total of the sums of every contiguous subarray.
public long SumOfAllSubarrays(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Math and number theory
- Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.
Related katas
- Multiply Numeric Strings Medium Free Schoolbook multiplication of numbers thousands of digits long.
- Modular Exponentiation Medium Free Raise to a power of 10^18 - one squaring at a time.
- How Many Sensor Rings Fit? Medium Free Count nonnegative sensor readings consistent with adjacent sums around a ring, without trying every possible first reading.
- Subarrays Divisible by K Medium Free Count the subarrays whose sum is divisible by k.