Given an integer array nums and an integer k, print the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

### Input Format

Input consists of two lines.

The first line contains a two integers n (size of array n) and k.

Second line contains n spaced integers.

### Output Format

Print count of subarrays divisible by k

### Example 1

**Input**

6 5 4 5 0 -2 -3 1

**Output**

7

**Explanation**

There are 7 subarrays with a sum divisible by k = 5:

[4, 5, 0, -2, -3, 1] [5] [5, 0] [5, 0, -2, -3] [0] [0, -2, -3] [-2, -3]### Constraints

1 <= nums.length <= 3 * 104

-10^4 <= nums[i] <= 10^4

2 <= k <= 10^4

## Solution of Subarray Sums Divisible by K:–

import java.util.*; import java.lang.*; import java.io.*; public class Main { public static void main (String[] args) throws java.lang.Exception { //your code here Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int arr[] = new int[N]; int count=0; for(int i=0;i<N;i++) { arr[i]=sc.nextInt(); } for(int i=0;i<N;i++) { for(int j=i+1;j<N;j++) { if((arr[i]+arr[j])%K==0) { count++; } } } System.out.println(count); } }

## Add a Comment