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.
This is the Java implementation of usinha02, all credit goes to him and his algorithm.
All I did is use another language and add comments for the community, as the solution was great but took me a while to understand each of the statements and why the last if was needed.
staticintdivisibleSumPairs(intn,intk,int[]arr){intpairCount=0;// create an array with length equal to all reminders// available to k (0 to k-1 reminders)int[]remainderCountList=newint[k];for(inti=0;i<arr.length;i++){intremainder=arr[i]%k;remainderCountList[remainder]++;}// Now that the remainders have been counted, all that// produced a remainder of 0, can only be paired // between themselves, so, if say, there were 4 // numbers, we can make up to six pairs // i.e. (0,1) (0,2) (0,3), (1,2), (1,3), (2,3)intexactCount=remainderCountList[0];// all elements against a subset of one less of itself// and only half the pairs can be usedpairCount+=(exactCount*(exactCount-1))/2;// Now, for all other remainders, pairs are of those// that are complementing remainders// i.e. if K = 5, remainders would be 0, 1, 2, 3, 4// we know that 0 has already been accounted for// so, next pairs are all of those in 1 with 4 and// all those in 2 with 3// So we only need to iterate through half of the// remaining remainders, and make sure that we don't// use a reaminder against itself for this calculationfor(inti=1;i<=k/2&&i!=k-i;i++){pairCount+=remainderCountList[i]*remainderCountList[k-i];}// Finally, there is one more case to consider, if K// yields an even number of remainders, the loop above// would have skipped the exact middle remainder.// i.e. for k = 4, remainders = 0, 1, 2, 3// 0 has been accounted for// 1 and 3 were paired up// 2 is missing// This last remainder behaves like the 0 remainder, // so, we need to pair the numbers against themselvesif(k%2==0){inthalfCount=remainderCountList[k/2];pairCount+=(halfCount*(halfCount-1))/2;}returnpairCount;}
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 →
This is the Java implementation of usinha02, all credit goes to him and his algorithm.
All I did is use another language and add comments for the community, as the solution was great but took me a while to understand each of the statements and why the last if was needed.