Code Logo

Count Windows With Sum Divisible

Published at25 Jul 2026
Created by
Easy 1 views
Like0

Given an array of integers and a window size k, count how many subarrays of length k have a sum that is divisible by 3. Return the count of such windows.

For example, in [1, 2, 3, 4, 5] with k=3, windows: [1,2,3] sum=6 (divisible by 3), [2,3,4] sum=9 (divisible), [3,4,5] sum=12 (divisible). Return 3. With k=2: [1,2] sum=3 (divisible), [2,3] sum=5, [3,4] sum=7, [4,5] sum=9 (divisible). Return 2.

This problem teaches sliding window with modular arithmetic. Instead of recomputing the full sum for each window, you maintain a running sum and update it incrementally as the window slides.

The solution computes the sum of the first k elements and checks divisibility. Then slides: subtract outgoing, add incoming, and check each new sum.

Edge cases include k larger than the array (return 0), an empty array (return 0), and negative numbers (the sum may be negative but divisibility by 3 still applies).

Example Input & Output

Example 1
Input
[3,6,9,12],3,3
Output
2
Explanation

[3,6,9]=18 and [6,9,12]=27 — both div by 3

Example 2
Input
[1,2,3,4,5],2,3
Output
2
Explanation

[1,2]=3, [4,5]=9 — both divisible by 3

Example 3
Input
[],2,5
Output
0
Explanation

Empty array

Example 4
Input
[1,3,5],2,2
Output
2
Explanation

[1,3]=4, [3,5]=8 — both divisible by 2

Example 5
Input
[2,4,6,8],2,6
Output
1
Explanation

[2,4]=6 divisible by 6

Algorithm Flow

Recommendation Algorithm Flow for Count Windows With Sum Divisible

Solution Approach

Use a sliding window to maintain the sum incrementally and check divisibility by 3.

function countDivisibleWindows(arr, k)
  if k > length(arr) or length(arr) == 0 then return 0
  count = 0, sum = 0
  for i = 0 to k - 1
    sum = sum + arr[i]
  if sum % 3 == 0 then count = count + 1
  for i = k to length(arr) - 1
    sum = sum - arr[i - k] + arr[i]
    if sum % 3 == 0 then count = count + 1
  return count

Sum the first window. Slide by subtracting the outgoing element and adding the incoming one. Check each cumulative sum for divisibility by 3 using the modulo operator.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums, int k, int d) {
        if(nums.length<k)return 0;
        int s=0;for(int i=0;i<k;i++)s+=nums[i];
        int r=s%d==0?1:0;
        for(int i=k;i<nums.length;i++){
            s+=nums[i]-nums[i-k];
            if(s%d==0)r++;
        }return r;
    }
}