There was a problem on hackerrank - (Link below)
And this is the link of solution -
https://www.hackerrank.com/rest/contests/w6/challenges/consecutive-subsequences/hackers/dhruvchandhok/download_solution
Please explain the algorithm and logic behind the solution
(Mainly why are we using ans+=a[i]*(a[i]-1)/2;) (Something like nC2)
Please help…
The contest has already blocked submission of the problem (So, I am not cheating)
Initially we are calculating the sum of numbers till ith element in array mod k and hashing it to an array.
Let the array be 1 2 1 2 1 2 and k = 2
So the hashed sum from beginning we get will be like :
i = 0 : hashedsum = 1;
i = 1 : hashedsum = 1;
i = 2 : hashedsum = 0;
i = 3 : hashedsum = 0;
…and so on.
Now let us observe one thing, that if any segment from L to R is divisible by k, then hashedsum[R] == hashedsum[L-1] (By principle of divisibility). So we can hash and calculate the number of places we get a hashedsum from o to k-1. And then apply the logic of choosing any two points where hashedsum is equal to any i. That gives you the NC2 logic in the loop, which leads you to the answer.
What is hashing???
I am a beginner and I am unaware of this concept.
Hi megatron_64,
if the input numbers are in array “arr” and “K” is given in the question.
Let me define prefix_sum[i] = arr[0] + arr[1] + … arr[i]
if prefix_sum[i] % K == prefix_sum[j]%K for i < j
then
For example prefix_sum[i]%K = 3, prefix_sum[j]%K = 3 for i < j
what it means ??? Just think… that is in between i and j there is array sum which is
divisible by K right ? ===> sum of array for indices (i, j] is divisible by K.
Now generalize this. Take an of size K:===> that is reminder[K]
for i 0 to N-1:
remainder[prefix_sum[i]%K]++
what the above means is… for a particular “remainder value”, store the count of indices where you are getting that remainder.
Lets take an example:
For remainder 3 assume indices which gives prefix_sum[i]%K == 3 are 5, 8, 10, 20, 23.
5, 8, 10, 20, 23 ==> so how many Subsequences are possible ???
[6-8],
[6-10], [9-10],
[6-20], [9-20], [11-20],
[6-23], [9-23], [11-23], [21-23].
So you got the logic right???
ans = (n*(n-1))/2
But for remainder “0” if there are indices 5, 8, 10, 20, 23.
like this, then there is small change. Because
[0-5], [0-8], [0-10], [0-20], [0-23] are also added as a correct Subsequences.
thats y we initialize remainder[0] = 1, else 0’s
Thats it 
Hashing is a way you map computed data. In this case, we find sum modulo k and store it in an array with index equal to the (sum % k). We are mapping the sum to a counter (for counting nc2 later on).