We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
A similar idea in C#. A bit more verbose, but I think the logic is a bit clearer.
It also avoids repeating the "n * (n - 1) / 2" formula twice.
publicstaticvoidMain(string[]args){// First input line contains n and k. Ignore n because it will be// implied by the second input line.intk=int.Parse(Console.ReadLine().Split(' ')[1]);// When reading the line, we only care about each value mod k.// Read the line in, and convert it to a dictionary/map with// value-mod-k as key, and the number of times that value-mod-k// occurs as the value.varmodCounts=Console.ReadLine().Split(' ').Select(x=>int.Parse(x)%k).GroupBy(x=>x).ToDictionary(x=>x.Key,x=>x.Count());// Initialize the resultintresult=0;// We only need to check the first k/2 keys (plus the middle key// if k is odd), because the other keys are "complementary" (may// not be the correct term, see comment below) to the ones we check.for(intmodValue=0;2*modValue<=k;modValue++){intmodCount;// If modCounts does not contain the key modValue, then modCount will// be 0.modCounts.TryGetValue(modValue,outmodCount);// "Complement" may not be the correct term for this. As I'm using it,// complement(n) with respect to k is defined as the value c// such that (n + c) % k == 0 and c % k == 0.varcomplementValue=(k-modValue)%k;if(modValue==complementValue){// If modValue == complementValue (which happens if modValue == 0,// or if modValue == (k + 1) / 2 and k is odd), then each occurrence// of modValue pairs with other occurrences of the same modValue.// The number of pairs within modCount identical values is// Sum (from i=1 to modCount-1) of i.// Sum (from i=1 to n) of n is ((n * (n + 1)) / 2), which is equivalent to// (n^2 + n) / 2. With n = modCount - 1:// ((modCount - 1)^2 + (modCount - 1) / 2// ((modCount^2 - 2 * modCount + 1) + (modCount - 1)) / 2// (modCount^2 - modCount) / 2result+=modCount*(modCount-1)/2;}else{// In the normal case, modValue != complementValue, we just have// modCount * complementCount pairs.intcomplementCount;modCounts.TryGetValue(complementValue,outcomplementCount);result+=modCount*complementCount;}}Console.WriteLine(result);}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Divisible Sum Pairs
You are viewing a single comment's thread. Return to all comments →
A similar idea in C#. A bit more verbose, but I think the logic is a bit clearer. It also avoids repeating the "n * (n - 1) / 2" formula twice.