fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int subarraysDivisible(vector<int>&arr, int n , int k){
  5. 	unordered_map<int,int>mpp;
  6. 	mpp[0]++;
  7. 	int ans = 0;
  8.  
  9. 	int prefixSum = 0;
  10. 	for(int i=0;i<n;i++){
  11. 		prefixSum += arr[i];
  12. 		int x = ((prefixSum % k) + k)%k;    // to handle negative 
  13. 		ans += mpp[x];
  14. 		mpp[x]++;
  15. 	}
  16. 	return ans;
  17. }
  18.  
  19. int main() {
  20. 	int n;
  21. 	cin>>n;
  22. 	vector<int>arr(n);
  23. 	for(int i=0;i<n;i++){
  24. 		cin>>arr[i];
  25. 	}
  26.  
  27. 	int k;
  28. 	cin>>k;
  29.  
  30. 	cout<<"Number of Subarrays divisible by k : "<<subarraysDivisible(arr,n,k);
  31. 	return 0;
  32. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
4
2 3 5 8 
2
stdout
copy 
Number of Subarrays divisible by k : 6
https://ideone.com/WXxEp8
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!