Subarray Divisibility Solution | CSES Problem | Number of subarray divisible by k

 

Subarray Divisibility

Given an array of n$n$ integers, your task is to count the number of subarrays where the sum of values is divisible by n$n$.

Input

The first input line has an integer n$n$: the size of the array.

The next line has n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$: the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints

• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• −109≤ai≤109$-{10}^9\le a_i\le {10}^9$
  

Example

Input:
5
3 1 2 7 4

Output:
1

	void solve() {
	// mii is map<int,int> and int is defined as long long int
	int n;
	cin>>n;
	int sum=0;
	int ans=0;
	mii m;
	m[0]=1;
	for (int i = 0; i < n; i++)
	{
	int x;
	cin>>x;
	sum+=x;
	int rem=sum%n;
	if(rem<0)rem+=n;
	ans+=m[rem];
	m[rem]++;
	}
	cout<<ans<<endl;
	}

Made with ❤ by Raunit Verma Rate Us 5⭐ Here