Skip to content
Katabench
Try free

Subarrays Divisible by K

Medium About 20 min Free, no account needed

Count the subarrays whose sum is divisible by k.

The brief

Given an integer array nums and a positive integer k, count the contiguous subarrays whose sum is divisible by k.

The performance bar

The obvious approach sums every subarray, O(n2). The hidden test has 150,000 elements where every subarray qualifies, so nothing short-circuits and the quadratic version is too slow. You need an O(n) sweep. Mind negative values when reasoning about divisibility.

Starter code

C#
using System;

public class Solution
{
    // TODO: return the number of contiguous subarrays whose sum is divisible by k.
    public long SubarraysDivByK(int[] nums, int k)
    {
        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 →

Related guides

What it practices

Prefix sums
Carry running totals or prefix state so any range question becomes a lookup.
Math and number theory
Replace enumeration with a formula: GCD, modular arithmetic, digit math and closed-form counting.

Do these first

Related katas