Subarray Sums Divisible by K

Problem Statement

Subarray Sums Divisible by K Problem Description Given an integer array a consisting of n elements, and an integer k , your task is to find the number of non-empty subarrays whose sum is divisible by k . A subarray is a contiguous part of the array. Input Format The first line contains two integers n and k (1 ≤ n ≤ 3 · 10 4 , 2 ≤ k ≤ 10 4 ). The second line contains n integers a 1 , a 2 , ..., a n (-10 4 ≤ a i ≤ 10 4 ). Output Format Print a single integer – the number of non-empty subarrays with sum divisible by k . Examples Example 1: Input: 6 5 4 5 0 -2 -3 1 Output: 7 Note: In the first example, there are 7 subarrays whose sum is divisible by 5: [4, 5, 0, -2, -3, 1] [5] [5, 0] [5, 0, -2, -3] [0] [0, -2, -3] [-2, -3] Example 2: Input: 7 4 3 1 -2 6 0 -3 2 Output: 7