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 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
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.
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
- Contiguous Array Medium Free Longest subarray holding as many zeros as ones.
- 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.
- Product of Array Except Self Medium Free For each index, return the product of all other elements, without division.