Skip to content
Katabench
Try free

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.

The performance bar

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

C#
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.

C# coding challenges →

What it practices

Math and number theory
Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.

Related katas