I am not able to understand why we are doing nC2 in this problem?

#1

In the tutorial sir did nC2 i am not able to understand the use of it.

#2

@Deepanshu_garg
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( freq[i] , 2 ) or simply freq[i] * (freq[i] - 1) / 2 .

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.