DSA problem
Subarray Sums Divisible by K
Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.
A subarray is a contiguous part of an array.
The brute-force approach of checking every subarray runs in O(n^2) time. The key observation is that a subarray sum from index i+1 to j is divisible by k if and only if the prefix sums at i and j have the same remainder when divided by k. By tracking how many times each remainder has been seen, we can count valid subarrays in a single pass. Care must be taken with negative numbers: in many languages the modulo of a negative value can be negative, so normalize the remainder into the range [0, k).
Examples
nums = [4,5,0,-2,-3,1], k = 57nums = [5], k = 90nums = [-1,2,9], k = 22Constraints
- 1 <= nums.length <= 3 * 10^4
- -10^4 <= nums[i] <= 10^4
- 2 <= k <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.