Help me resolve time limit error in this program

#1

code link is -

problem is divisible subarrays

#2

Hello Raghav,
First of all you have missed out the condition while computing the cumulative sum when the sum gets negative.
At such a point you are supposed to make it positive and then take modulo
sum = (sum+n)%n;

As for the TLE , you are getting a TLE for the nested loops at the end of each testcase. We don’t need those loops to get the answer. You can get the final ans using the formula

ans = ans + (no *(no-1))/2 ;

Explanation : In this problem we simply need to choose the indices where the cumulative sum is same after taking the modulo. We use the combination formula - C(cumSum[i] , 2) for each index .

This will give you the ans for each index. Now just add all those values to get your final ans.
Thus we get the answer in O(n) complexity rather than O(n^2).

#3

i dont understand the logic behind the combination formula. why do we need that? please give more explanation/

#4

We are going to implement Pigeonhole Principle in this problem. Make a frequency array, lets call it freq[ ] , where are we are going to store the frequency of cumulative sums after taking modulo with n.
For example , say the array we get in input is { 1 , 2 , 2 ,6 ,7 }
The Cumulative sum array we get after taking the modulo is { 0 , 1, 3 , 0 , 1 , 3 } (Size of cumSum array is one more than n as the first cumSum before we count any element is 0 - The NULL subarray )

Our freq array in this case becomes
( Represented as Index->Value)
0 -> 2 (As 0 occurs twice in cumSum array)
1 -> 2 (1 occurs twice as well)
2 -> 0 (Occurs 0 times)
3 -> 2
4 -> 0

Note that the size of freq array will be equal to n as the sum will never exceed n (Since we are taking the modulo with n)

Now we run a loop over this freq[ ].
Implement the combination formula. This is where the pigeonhole principle comes into play as it assures us that there would atleast be one such integer having value 2 in the freq[ ] .

Looking at the cumSum array we can say that only the subarrays will be divisible where the cumSum value is same after taking modulo. You can check this for this example or any other.

Since we have already taken all the occurrences of cumSum in the freq[ ] , we simply use the combination formula

ans = ans + (no * (no - 1) )/ 2;

Since we need to choose any two occurrences with the same cumSum value and that would give us one divisible subarray.