Subordinate graphs divisible by K

Question

Given a sequence of n natural numbers, we need to count consecutive subsequences, the sum of which is divided by k.

Limitations: N to 10 ^ 6, and each item to 10 ^ 9 and K to 100

EXAMPLE: Let N = 5 and K = 3, and the array - 1 2 3 4 1

Here is the answer 4

Explanation: There are 4 subsequences, the sum of which is divided by 3, they

3 1 2 1 2 3 2 3 4 

My attempt:

 long long int count=0; for(int i=0;i<n;i++){ long long int sum=0; for(int j=i;j<n;j++) { sum=sum+arr[j]; if(sum%k==0) { count++; } } } 

But obviously, his bad approach. Can they better approach this issue? Please, help.

Complete the question: https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences

Answer 1

Here is a quick solution to O (n + k):

1) Allows to calculate prefix sums pref [i] (for 0 <= i <n).

2) Now we can calculate count [i] - the number of prefixes with the sum i modulo k (0 <= i <k). This can be done by iterating through all the prefixes and doing count [pref [i]% k] ++. Initially, count [0] = 1 (an empty prefix has the sum 0) and 0 for i! = 0.

3) The answer is the sum of count [i] * (count [i] - 1) / 2 for all i.

4) It is better to calculate the prefix sums modulo k to avoid overflow.

Why does it work? Let's go closer to the submatrix divisible by k. Let's say that it starts in the L-position and ends in the R-position. It is divisible by k if and only if pref [L - 1] == pref [R] (modulo k), since their difference is equal to zero modulo k (by the definition of divisibility). Thus, for each fixed modulo we can choose any two prefixes with this prefix sum modulo k (and there is exactly an account [i] * (count [i] - 1) / 2 ways to do this).

Here is my code:

 long long get_count(const vector<int>& vec, int k) { //Initialize count array. vector<int> cnt_mod(k, 0); cnt_mod[0] = 1; int pref_sum = 0; //Iterate over the input sequence. for (int elem : vec) { pref_sum += elem; pref_sum %= k; cnt_mod[pref_sum]++; } //Compute the answer. long long res = 0; for (int mod = 0; mod < k; mod++) res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1) / 2; return res; } 

Answer 2

This should make your calculations easier:

 //Now we will move all numbers to [0..K-1] long long int count=0; for(int i=0;i<n;i++){ arr[i] = arr[i]%K; } //Now we will calculate cout of all shortest subsequences. long long int sum=0; int first(0); std::vector<int> beg; std::vector<int> end; for(int i=0;i<n;i++){ if (arr[i] == 0) { count++; continue; } sum += arr[i]; if (sum == K) { beg.push_back(first); end.push_back(i); count++; } else { while (sum > K) { sum -= arr[first]; first++; } if (sum == K) { beg.push_back(first); end.push_back(i); count++; } } } //this way we found all short subsequences. And we need to calculate all subsequences that consist of some short subsequencies. int party(0); for (int i = 0; i < beg.size() - 1; ++i) { if (end[i] == beg[i+1]) { count += party + 1; party++; } else { party = 0; } } 

So, with the maximum size of the array = 10 ^ 6 and the maximum size of the remainder = 99, you will not have overflow, even if you need to sum all the numbers in a simple int32.

And the time you spend will be around O (n + n)