Author: yashu2040
Tester: pulkit_0110
Editorialist: yashu2040
DIFFICULTY:
EASY-MEDIUM.
PREREQUISITES:
Hashing,prefix sums
EXPLANATION
First observe that if we divide array elements by 1e8 ,then question reduces to Count subarrays with sum divisible by 10.
We can iterate over array elements and store the count of cummulative sum(0 to i) modulo 10 in map or set .
If that sum has occurred before, lets suppose at index j,then we have found our subarray (j+1 to i).Then we simply increase our answer by cnt[current_sum].
Here is the code:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
main()
{
int t;
cin >> t;
while(t–)
{
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] /= 100000000;
}
int ans = 0;
map<int, int> cnt;
cnt[0]++;
int cur = 0;
for(int i = 1; i <= n; i++)
{
cur += a[i];
cur %= 10;
ans += cnt[cur];
cnt[cur]++;
}
cout << ans << endl;
}
return 0;
}