# Divisible Sum Pairs

# Divisible Sum Pairs

usinha02 + 44 comments # I did this in O(n)

## If any suggestions please let me know

using namespace std; int main(){ int n; int k; cin >> n >> k; int a[n]; int m[k]; for(int i=0; i<k; i++) m[i]=0; for(int i = 0; i < n; i++){ cin >> a[i]; m[a[i]%k]++; } int sum=0; sum+=(m[0]*(m[0]-1))/2; for(int i=1; i<=k/2 && i!=k-i; i++){ sum+=m[i]*m[k-i]; } if(k%2==0) sum+=(m[k/2]*(m[k/2]-1))/2; cout<<sum; return 0; }

Noroi + 3 comments Can you please explain the logic here of how did you deduce the total number of pairs modding to k?

petreeftime + 17 comments The idea is that you separate elements into buckets depending on their mod k. For example, you have the elements: 1 3 2 6 4 5 9 and k = 3

`mod 3 == 0 : 3 6 9 mod 3 == 1 : 1 4 mod 3 == 2 : 2 5`

Now, you can make pairs like so: Elements with

**mod 3 == 0**will match with elements with**(3 - 0) mod k = 0**, so other elements in the**mod 3 == 0 list**, like so:`(3, 6) (3, 9) (6, 9)`

There will be

**n * (n - 1) / 2**such pairs, where**n**is length of the list, because the list is the same and**i != j**. Elements with**mod 3 == 1**will match with elements with**(3 - 1) mod k = 2**, so elements in the**mod 3 == 2**list, like so:`(1, 2) (1, 5) (4, 2) (4, 5)`

There will be

**n * k**such elements, where**n**is the length of the first list, and**k**of the second.Because you don't need to print the actual pairs, you need to store only the number of elements in each list.

Noroi + 1 comment Thanks this lays it down pretty good. This should be in the editorial.

danjb + 2 comments It is an optimal solution, but keep in mind: Reading the input sizes is really important in a competition. Here we have N <= 100 and it would be a waste of time to implement the optimal solution. For N <= 10^9 however, this optimal solution would be better.

bgenchel + 1 comment if the processing is trivial on the inputs, as in the case of processing the mod counts, why should input size matter?

danjb + 0 comments Small input size: You don't have to think that hard and you can implementend a simpler solution, which needs less time to write the code for and debug.

petreeftime + 1 comment Yes, but this second solution is a better learning tool for modular arithmetics. The other solution is trivial.

aarohiagarwal12 + 2 comments Don't you think this might increase the space complexity if k>10 or something..??

lovereli + 0 comments There is always a tradeoff between space and time complexity. Otherwise we might be in a better world!!

jwiener88 + 0 comments The space complexity can be reduced to O(min(n,k)) if a hashtable is used instead of an array. So space complexity and time complexity both scale linearly.

Jyothi_sirigi + 1 comment But in the problem it is given as we have to print the number of (i,j) pairs and the given condition is i

Khoa190602 + 0 comments It said to print the number of pairs not the pairs themselves

kiamottullah + 0 comments hey please tell me that which algorithom or any other books are u flowing >?

prakashk885 + 0 comments [deleted]Jlookup + 8 comments Thanks @usinha02 for the algo, and @petreeftime for the explanation. Here's an implementation in Python. Some bits are a little clunky. Feedback Please.

Python 3:

import sys n,k = [int(x) for x in input().strip().split(' ')] a = [int(a_temp) for a_temp in input().strip().split(' ')] mods = [0] * k for i in range(n): mods[a[i] % k] += 1 count = 0 for i in range(int(k/2) + 1): if i == 0: count += int(mods[0] * (mods[0] - 1) / 2) elif float(i) == (k/2): count += int(mods[int(k/2)] * (mods[int(k/2)] - 1) / 2) else: count += int(mods[i] * mods[k-i]) print (count)

SebastianNielsen + 12 comments What time complexity is that? Is it better than mine?

n,k = (int(x) for x in input().split()) lst = list(map(int, input().split())) count = 0 for i in range(len(lst)-1): for x in range(1+i, len(lst)): if (lst[i] + lst[x]) % k == 0: count += 1 print(count)

emptyset + 0 comments [deleted]surajt_oneliner + 0 comments fab man :)

LeHarkunwar + 7 comments How about this in python ?

def divisibleSumPairs(n, k, ar): return sum(1 for i in range(n) for j in range(n) if i < j and (ar[i]+ar[j])%k == 0)

ghosh_saikat4000 + 0 comments It's quadratic ... Less lines of code doesn't necessarily mean less time complexity.

malexand314 + 0 comments It's the exact same solution as above from SebastianNielsen, just in a one-line format.

Ravitejacms + 0 comments Awesome!!

washinpi + 2 comments i think this code will take less runtime than yours :)

def divisibleSumPairs(n, k, ar): # Complete this function return sum(1 for i in range(n) for j in range(i+1 ,n) if (ar[i]+ar[j])%k == 0)

157926_pradip + 0 comments Your code will take O(n^2) time complexity.

jaymzdee + 2 comments Use combinations...

def divisibleSumPairs(n, k, ar): # Complete this function return len([x for x in combinations(range(n), 2) if (ar[x[0]]+ar[x[1]])%k==0])

sd_afzal_hussain + 0 comments def divisibleSumPairs(n, k, ar): from itertools import combinations return len([com for com in combinations(ar, 2) if sum(com) % k == 0])

ritikjain51 + 0 comments Think when you have n = 100. Then number of combinations are 4095. Which is too much to compute.

rakesht2499 + 0 comments What about this

return sum([1 for i,x in enumerate(ar) for y in ar[i+1:] if (x+y)%k == 0])

raghavpaliwal291 + 0 comments your code is not optimal it will not work for large numbers

skanth004 + 4 comments I did the same logic in java :)

for(int i=0; i<n; i++){ for(int j=1;j<n;j++){ if (i < j){ a = ar[i] + ar[j]; if (a % k == 0){ count++; }} } }

skanth004 + 1 comment [deleted]shradhaagar_09 + 0 comments my code is same but then also it is not able to pass some test cases

LukeRocheDev + 5 comments works but is hard to read... i would do

for(int i=0; i<n-1; i++){ for(int j=i+1;j<n;j++){ a = ar[i] + ar[j]; if (a % k == 0) count++; } }

bytes_and_bits + 4 comments It does not pass all test cases

correia_mario + 1 comment [deleted]correia_mario + 0 comments [deleted]

correia_mario + 1 comment work to me

count=0; for(i=0;i<(ar.length)-1;i++) for(j=i+1;j<(ar.length);j++) if((ar[i]+ar[j])%k==0) count++; return count;

akhilmohandas + 2 comments how does this pass all the tests when the ar[i] less than ar[j] is not performed?

TopazJ + 3 comments ar[i] will always be less than ar[j] since j is initialized as i+1 and increments...

balint_imal + 0 comments [deleted]frashure + 0 comments [deleted]frashure + 0 comments [deleted]

palashrawat7 + 1 comment ar[i] would be less tha ar[j] always as ar[j] is initialized as i+1. So it will always be 1 value bigger than i.

frashure + 0 comments [deleted]

sanchitgnawali + 0 comments make sure you use

a = ar[i] + ar[j]

my solution was similar but didn't pass the all the test cases because i was using

a = i+j

Masthan + 0 comments for(int i=0; i

Iancarson01 + 0 comments But basically its the same concept with that of @skanth004

alokk830 + 0 comments Where are you comparing the values of ar[i] and ar[j], which is the necessary condition in the given problem statement. You have to compare whether the ar[i] < ar[j]

Masthan + 0 comments that's optimal

csk111165 + 0 comments Simple and crisp!

cs_1716410184 + 0 comments [deleted]anirudh_kushwah1 + 0 comments why is this isn't working?

int counter=0; for(int i=0;i

baduker + 1 comment Why are we substracting 1 from the array length in the first loop?

juri_the_eagle + 0 comments Cause the second number has to be at a later position, there's never a pair for the last position.

chinmay43 + 0 comments How about this? Here is my Python 3 code: I used combinations

def divisibleSumPairs(n, k, ar): sum_lst = list() res = list() comb_list = (list(combinations(ar, 2))) for i in comb_list: sum_lst.append(i[0] + i[1]) for i in sum_lst: if (i % k) == 0: res.append(i) return (len(res))

ritikjain51 + 0 comments O(n^2) It is.

luboyswag + 0 comments Why the range(len(lst) - 1)?

vasilij_kolomie1 + 0 comments the same:

return list((ar[i]+ar[j])%k for i in range(n) for j in range(n) if i < j).count(0)

peter_augustinak + 0 comments Where are you handling that i < j in this code?

brendonbeni42 + 0 comments same logic what I did but i miss the second loop 1+i,so i get more number of possible pairs.Thank man!.

2016_rohit_dora1 + 0 comments can you please explain the 2 for loops

oliver_hare + 6 comments Slightly simpler O(n) python3 code

def divisibleSumPairs(n, k, ar): nums = [0] * k count = 0 for ele in ar: modu = ele % k count += nums[(k - modu) % k] nums[modu] += 1 return count

Token_404 + 0 comments [deleted]toosengzhao + 1 comment Could you provide some explanations to this? Appreciate it lots!

djaychela + 1 comment I've just spent half an hour looking through this and the parent comments above (which are given some credit for the idea) - it's a really clever solution to the problem, and if you read petreeftime's description above, it covers it pretty well. I found a key to understanding it was to alter the code so that you see the contents of all the relevant variables at each step, and then it became clear how it was working (I'm using Python 3.6, hence the f strings):

def divisibleSumPairs(n, k, ar): nums = [0] * k count = 0 for ele in ar: modu = ele % k print(f"{ele} {modu} {count} {nums} - after modu") count += nums[(k - modu) % k] print(f"{ele} {modu} {count} {nums} - after count+=") nums[modu] += 1 print(f"{ele} {modu} {count} {nums} - after nums+=") print("-----------------------") return count

The first step works out the mod value of the current array element - that's really the only thing that matters - a 3 and a 6 will have the same effect as a 3 and a 3 (for a k of 3).

Next step is to increment the counter by the number of possible combinations that yield k mod 0.

The third step adds the current array element to the nums list, which will allow that to be counted towards future possibilities in other steps.

felix_jatmiko + 0 comments The second step exists because ((k - modu % k) + (modu % k)) % k == 0.

nivedpk1994 + 0 comments brilliant logic

djaychela + 0 comments Great - just spent half an hour trying to work out how this worked, and now I have I feel like I've achieved something today! Thanks for the code.

trgiangvp3 + 0 comments God

kumsavarthami + 1 comment what does o(n) means?

Mublan + 0 comments same here

amaals_emam + 1 comment count += int(mods[0] * (mods[0] - 1) / 2) from where did this equation come up?

rajusujan2020 + 0 comments because n*n-1/2 pairs are available

aarohiagarwal12 + 0 comments Can you please explain, why is this part used?

elif float(i) == (k/2): count += int(mods[int(k/2)] * (mods[int(k/2)] - 1) / 2)

dtyagi1 + 0 comments print sum(1 for i in itertools.combinations(ar,2) if sum(i)%k==0)

Dimple151997 + 0 comments can u explain the code

rahulrajpl + 1 comment Why is this so complex?

def divisibleSumPairs(n, k, ar): # Complete this function count = 0 for i in range(n-1): j = i+1 while j < n: if ((ar[i] + ar[j]) % k) == 0: count += 1 j += 1 return count

singhnavpreet + 1 comment U wont understand

rahulrajpl + 0 comments

Palak7 + 0 comments def divisibleSumPairs(n, k, ar): count = 0 for i in range (n): for j in range(i+1,n): if ((ar[i]+ar[j]) % k) == 0: count += 1 return count

**How about this?**

smdaziz + 0 comments Thanks for the explanation petreeftime! How does it take care of choosing only those pairs whose index i < j?

tanzeelosama + 0 comments GENIOUS!

vikki_kumar + 0 comments Thanks this is really helpfull.

ShikamaruNara + 0 comments But what happens when mod 3=0 elemtns are all {3,3,3} There would be no pairs in bw them , but as per your solution , we would get 3 again ??

sri_sam229 + 0 comments good logic but i am interested to know if that helped any complexity.

ShivendraKadam + 0 comments Nice explaination Thank You

kharatpriyank + 0 comments Thank you usinha02 for the elegant solution, and thank you petreeftime for an awesome explanation! Although I understood most of it, and this maybe most naive doubt that I have. I wasn't able to understand the following condition:

if(k%2==0) sum+=(m[k/2]*(m[k/2]-1))/2;

Thanks in advance.

asiyer + 0 comments When you say, n is the length of the first list, and k the length of the second, do you mean the list of mod3 == x ?or the input list?

doublelixr + 0 comments Elements with mod 3 == 0 will match with elements with (3 - 0) mod k = 0

That sentence is kind of confusing because k is 3 in this case.. I think you meant in general, matching buckets with

**mod k == x**and**mod k == k - x**hemanggupta3 + 0 comments why are we running the loop till k/2?

jm_leddy + 0 comments You really should have used an even number to explain the middle bucket and this case better:

`if(k%2==0) sum+=(m[k/2]*(m[k/2]-1))/2;`

Edit:

Say with k= 4, you have 1 3 2 6 4 5 9 10:

`mod 4 == 0 : 4 mod 4 == 1 : 1 5 9 mod 4 == 2 : 2 6 10 mod 4 == 3 : 3`

The base case is the same, and

**mod 1**matches with**mod 3**, as before. However, we also have (2, 6) (2, 10), and (6, 10)This follows the same logic as the bass case, where any number in this list can match any other number in this list, thus we also use

**n * (n-1) / 2**here as wellSpleen + 0 comments Excellent. Really thank you for your explanations guy :O

ghcho20 + 0 comments [deleted]imnetanmangal + 0 comments Please use better variable names It makes other fellows easy to understand

delight182 + 0 comments Isn't it O(n + k) (or O(max(n, k)))? You actually don't need to iterate over m, see my O(n) solution.

Also, I didn't run your code but your result looks off by m[k/2]*m[k/2-1] because your termination condition is i<=k/2 (should be i<k/2 as you handle this case separately).

Otherwise you got the idea right, good job!

wkusnierczyk + 0 comments This is

*O(n + k)*, not*O(n)*.In particular, when

`n = 0`

you have:--

*O(k)*space allocation (`m[k]`

)

--*O(k)*run time (`for(int i=1; i<=k/2 && i!=k-i; i++)`

loop).MisterHax + 1 comment For anyone that wishes for a little more background like I did on this stuff, I found the explanations of modular arithmetic on Khan Academy really helpful.

for(int i = 0; i < n; i++){ cin >> a[i]; m[a[i]%k]++; }

This above piece of code is just finding the amount of elements in each "equivalence class" and all code after that is taking advantage of the addition property of modular arithmetic:

(A+B) mod C = ((A mod C) + (B mod C)) mod C

Hope this helps out there! Great solution!

de_ganxta + 0 comments thanks

ghcho20 + 1 comment I have a question.

for (int i=1; i<=k/2 && i!=k; i++) sum += m[i]*m[k-i];

Here, m[i] seems not to have information about the order.

Does it meet the constraint of i<j ?

Looks like it does not tell (1,5) and (5,1).petreeftime + 1 comment In this case i is at most k/2 = 2 and k - i is at least k - k/2 = 3, you can only have (1, 5). This is also true for any other example.

ghcho20 + 1 comment I'm afraid I don't get it right.

Let me rephrase the question.

For k=6, if you have input '1, 5, ... , 5, 1'

Both first & second '1' enters m[1] slot

Likewise both '5' to m[5] slot

m[i]*m[k-i] count both anyhow (for i <= k/2)

But (5,1) must not count because of i<j constraint.

Am I missing something ?

thanksantipyrrhus + 0 comments No. For your example with k=6, if the input were [a0,a1,a2,a3] = [1,5,5,1], then both of the (5,1) (that is, (a1,a3) and (a2,a3)) count because in both cases i < j. (1 < 3 and 2 < 3)

irshad_ck + 6 comments You can use this logic to reduce the code. {

int count

for(int i = 0 ; i <= n; i++){

`for(int j = 0; j < n; j++ ){ if(i < j){ if((a[i]+a[j])%k == 0){ count++; } } } }`

}

marigabibenitez + 0 comments [deleted]tourofer + 0 comments [deleted]abhilashpani651 + 0 comments it displays floating point exception

jay209 + 0 comments It has O(n^2) complexity!

prabhjot8126 + 4 comments you could have done like this could reduce little more

for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if((a[i]+a[j])%k==0) { count++; } } }

hira89 + 3 comments I came up with same logic, but for input 6 3 1 3 2 6 1 2 my answer is 10 instead of 5.. i think its counting reverse combination too. ex: 0,3 and 3,0 if its divisible by k.

prabhjot8126 + 3 comments @hirababu089 there is no possible way for which it could make a pair such as (3,0) becouse in the second loop the smallest value possible is i+1 (the inital j position) anyways here the entire code may be you are doing some silly mistake like putting j=1 instead of j=i+1; in second loop

#include <math.h> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <assert.h> #include <limits.h> #include <stdbool.h> int main() { int n; int k; int count=0; scanf("%d %d", &n, &k); int *a = malloc(sizeof(int) * n); for(int a_i = 0; a_i < n; a_i++){ scanf("%d",&a[a_i]); } for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if((a[i]+a[j])%k==0) { count++; } } } printf("%d",count); // write your code here return 0; }

MARVELMafia + 2 comments Instead of using two loops why not just use one? Like mine:

for(int i=0;i<n;i++) { val=a[i]+a[i+1]; if(val%k!=0) { count++; } }

dinesh_pi + 0 comments these can only find consecutive pairs

audusheriffemor1 + 0 comments this will find the opposite of what we are looking for.

prasanna_STR + 0 comments I thinks its wrong

anshumanc007 + 0 comments see instesd of writing j=i+1; we add a condition if(A[i]>A[j]);then sum=A[i]+A[j] else sum=1 then if sum%k==0 c=c+1 it will not work?????

satyambhalla17 + 0 comments Also check for the condition where i < j then increment the count variable.

jyoshu + 0 comments [deleted]

mikepare93 + 0 comments I did something similar and passed. I'm pretty sure this type of solution is O(nlogn).

varun_1995 + 0 comments run outer loop for i < n - 1

logasanjayr5055 + 0 comments this will eliminate the comparison of certain numbers

anicse0904071 + 0 comments the first loop doesnt need to loop through i<=n , it should loop through i< n-1, because i should always be less than j .

marigabibenitez + 0 comments [deleted]erichamion + 1 comment 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.

public static void Main(string[] args) { // First input line contains n and k. Ignore n because it will be // implied by the second input line. int k = 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. var modCounts = Console.ReadLine() .Split(' ') .Select(x => int.Parse(x) % k).GroupBy(x => x) .ToDictionary(x => x.Key, x => x.Count()); // Initialize the result int result = 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 (int modValue = 0; 2 * modValue <= k; modValue++) { int modCount; // If modCounts does not contain the key modValue, then modCount will // be 0. modCounts.TryGetValue(modValue, out modCount); // "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. var complementValue = (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) / 2 result += modCount * (modCount - 1) / 2; } else { // In the normal case, modValue != complementValue, we just have // modCount * complementCount pairs. int complementCount; modCounts.TryGetValue(complementValue, out complementCount); result += modCount * complementCount; } } Console.WriteLine(result); }

burak54 + 0 comments My eyes bleed. Too much comment lines.

bozhko_maksim_s1 + 4 comments If anyone is interested here is more modern and clear way of doing the same thing.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n, k; cin >> n >> k; vector<int> complenemts(k); int count = 0; int temp; for (int i = 0; i < n; ++i) { cin >> temp; int remainder = (temp % k); int complenemt = (k - remainder) % k; count += complenemts[remainder]; complenemts[complenemt] += 1; } cout << count; return 0; }

plasmashadowx + 0 comments Could you please explain the aspect behind it.

Merter_Sualp + 2 comments That's great. My Java version is here:

public class DivisibleSumPairs { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); Map<Integer, Integer> buckets = new HashMap<>(); int pairs = 0; for(int a_i=0; a_i < n; a_i++){ int num = in.nextInt(); num %= k; int complement = (k-num) % k; Integer count = buckets.get(complement); if (count != null) { pairs += count; } count = buckets.get(num); if (count == null) { buckets.put(num, 1); } else { buckets.put(num, count+1); } } System.out.println(pairs); } }

aman17 + 0 comments How does this solution take care of the condition i < j ?

daft_leech + 0 comments This is way simpler in Java 8

return IntStream.range(0,n).map(x -> IntStream.range(x+1,n).map(y -> (ar[x]+ar[y])%k==0?1:0).sum()).sum();

Axesilo + 0 comments Yes, this is exactly the algorithm I came up with too. Wrote mine in Swift:

import Foundation let readSplitter: () -> Array<Int> = { readLine()!.components(separatedBy: " ").map{Int($0)!}} let nk = readSplitter() let k = nk[1] let values = readSplitter() var buckets = [Int](repeating: 0, count: k) var pairCount = 0 for value in values { let modded_value = value % k let complement = (k - modded_value) % k pairCount += buckets[complement] buckets[modded_value] += 1 } print(pairCount)

chintanckg + 1 comment Can you place explain the logic.

jay209 + 3 comments public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; int count = 0; for(int a_i=0; a_i < n; a_i++){ int num = in.nextInt(); int remainder = num % k; int complement = (remainder==0)?k:remainder; count += a[k - complement]; a[remainder]++; } System.out.println(count); } }

Perhaps this would be easy to understand for you. First of all we save the remainder and then we take its complement to make a pair. For example, in the sample test case, if the remainder is 1, then we will take its complement which is 2, and we will look for a number if divided, would give a remainder 2. Therefore, the sum of this pair will be divisible by 3 (which is k). Also, it gives O(n) solution.

tochicool + 0 comments Excellent solution and equivalent code; really helped my userstanding of the efficent solution!

**Note:**There is a problem where you declare the size of the bucket array; it should be of size*k*, rather than*n*.theshishodia + 0 comments Just had a small doubt, suppose the array is {15, 16, 17, 18, 19}, total size of 'a' will be 5. Now suppose k = 31. Then a[31 - 15] = a[16], which will be out of bounds. same will happen with a[15];

robertoxxx931 + 0 comments can anyone describe whats happening here step by step?

jpan127 + 0 comments I did something like this for if k=3. Then realized k did not have to be 3 and gave up on that.

replytojain + 0 comments Here is an O(n) time solution. However, it does need O(n) space in worst case. Makes sense? Language: C#

public static void CountMatch(int[] num, int k){ int count = 0; //store mod and such counts Dictionary<int,int> dict = new Dictionary<int, int>(); foreach(int n in num){ int mod = n%k; int need = (k-mod) % k; //check if the dictionary has the balance if(dict.ContainsKey(need)){ count += dict[need]; } //increment/add mod to dictionary if(dict.ContainsKey(mod)){ dict[mod]+=1; } else{ dict.Add(mod, 1); } } Console.WriteLine(count); }

ghosh_saikat4000 + 0 comments Great solution ! Very elegant. Should be the editorial. Is there a similar solution if the question was to find divisible sum triplets ?

prabuddha62 + 1 comment Why is the if case(if(k%2==0)) needed?

ghosh_saikat4000 + 0 comments Elements with a remainder of 0 mod k, are paired with elements in the SAME residue class. So, we shouldn't just multiply here because we will be overcounting. So, we need choose(m, 2), where m is the number of elements mod 0. I have implemented this logic in another way here ... https://www.hackerrank.com/challenges/divisible-sum-pairs/submissions/code/45490290

Check it out. It might help.

LeHarkunwar + 1 comment How's this for python ?

def divisibleSumPairs(n, k, ar): return sum(1 for i in range(n) for j in range(n) if i < j and (ar[i]+ar[j])%k == 0)

dheeraj13997 + 0 comments [deleted]

akabeast + 1 comment I am missing something why is below two pieces of code different

count += rem[k/2] * (k%2 == 0) ? (rem[k/2] - 1) / 2 : rem[k/2] - i;

and

if( k%2 == 0) count += (rem[k/2] * (rem[k/2]-1)) / 2; else count += rem[k/2] * (rem[k-i]);

ghosh_saikat4000 + 0 comments a*b/2 is different from a*(b/2)

2*3/2 = 6/2 = 3

2*(3/2) = 2*1 = 2

agnivabasak1 + 0 comments This solution seems really awesome to me ,but can someone please explain why the condition i!=k-1 is imposed(maybe with soem examples) .And also why and how the last condition(i.e , if(k%2==0)) implemented .Thanks!

codertoaster + 0 comments [deleted]varun_1995 + 0 comments @usinha02 Your solution was really well thought out. Thanks.

alphazygma + 1 comment 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.

static int divisibleSumPairs(int n, int k, int[] arr) { int pairCount = 0; // create an array with length equal to all reminders // available to k (0 to k-1 reminders) int[] remainderCountList = new int[k]; for (int i = 0; i < arr.length; i++) { int remainder = 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) int exactCount = remainderCountList[0]; // all elements against a subset of one less of itself // and only half the pairs can be used pairCount += (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 calculation for (int i = 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 themselves if (k % 2 == 0) { int halfCount = remainderCountList[k/2]; pairCount += (halfCount * (halfCount-1)) / 2; } return pairCount; }

mahdijudeh + 0 comments Thank you for writing this out. Made me realize truly how great his was.

guner_batuhan + 0 comments i didnt understand your code. but here is another algorithm works with O(n)

def search(numbers,k): numberofways=int() for i in range(len(numbers)-1): for j in range(i+1,len(numbers)): if (numbers[i]+numbers[j])%k==0: numberofways+=1 return numberofways number=list() n=int(input()) k=int(input()) for i in range(n): number.append(int(input())) print(search(number,k))

tommyangkkasatr1 + 0 comments static int divisibleSumPairs(int n, int k, int[] ar) { // Complete this function int zero=0, one=0, two=0; for(int i=0;i

iceh22 + 0 comments Here is a Ruby version of your algorithm (where ar is the array of numbers):

def divisibleSumPairs(n, k, ar) pairs = 0 h = Hash.new(0).tap { |h| ar.each { |num| h[num%k] += 1 }} h.each do |key, val| compatikey = k - key compatival = h[compatikey] if key == compatikey || key == 0 pairs += ((1..(val-1)).inject(:+) || 1) if val > 1 elsif compatival > 0 pairs += (val * compatival) end h.delete(key) h.delete(compatikey) end return pairs end

7u5h4r + 0 comments But you used much more space suppose k is 2^30 then a array would occupy much more space

blackjar72 + 0 comments [deleted]aiswarya110498 + 0 comments your logic is amazing.. could you please explain this program in a clear manner..

vajjasaikiran444 + 0 comments Hey in the question it is asked to print the no. of pairs where a[i] +a[j] is divisble by k such that

**i is always less than j**.Are you following the element order?Because you are just storing the mod0, mod1, mod2 values in an array.But it does not keep track of the order of i and j.Thanks!Correct me if I am wrongCode_monk_01 + 0 comments I couldnot understand the for loop condition i != k-i

ilya_zarembsky + 0 comments Clever!

yashiagarwal1812 + 0 comments why is sum +=(m[0]*(m[0]-1))/2; having such a value also explain for loop after it

vasilij_kolomie1 + 0 comments I am dont understand a bit. what about k = 10000000000000000000000000000000000000000001 ? in Python it goes and how much memory will You use?

Or i am misstaking?

sajjadbashar + 0 comments def divisibleSumPairs(n, k, ar): # a map to store counts of each modulu class mods = k*[0] # counting each class for num in ar: mods[num%k]+=1 count = 0 for num in ar: # this will maintain i < j mods[num%k]-=1 # second module takes care of case mod == k mod = (k - num%k)%k count += mods[mod] return count

Thinkster + 0 comments For those looking into Ruby:

def divisible_sum_pairs(ar_length, array, k) temp, count = [0] * k, 0 array.each do |el| count += temp[(k - el % k) % k] temp[el % k] += 1 end p count end

kbkr_24794 + 0 comments Can somebody please explain, how

**i < j**condition is checked in this solution.ErikE + 0 comments Try the following inputs with your algorithm and see if the right answer of 0 is returned. I think your algorithm needs a tweak, and so does the problem. If I am wrong, I'll eat humble pie, but I've double-checked and I'm pretty sure about this.

5 2 1 1 1 1 1

or:

5 2 0 0 0 0 0

justinbieberfanz + 0 comments The complexity can drastically increase if k>10^6 . Anyways, thanks :-)

apple60126 + 0 comments a corner case can happen when all the input are in the same bucket then complexity will still be O(n^2)

yogeshmahawar93 + 0 comments welldone mate. Very amazing code

abrarmalekji1234 + 0 comments Very Nice

shubhamrai792 + 0 comments Can you explain the logic if k is even?

geoffhuang_cs + 0 comments This is O(n+k); sometimes k could be much bigger than n. If you actually want O(n), use a hashmap.

nvinson234 + 0 comments Wouldn't this actually be O(n+k)?

Not critizing as the Python solution I came up with (given below) is basically the same idea and would have the same bounds.

def divisibleSumPairs(n, k, ar): mod = [0 for i in range(k)] count = 0 for i, v in enumerate(ar): addend = (k - v % k) % k count += mod[addend] mod[v % k] += 1 return count

asheeshjanghu + 0 comments Brilliant. I used the same approach, but your code is more beautiful. Learnt something new from your code.

Palak7 + 0 comments def divisibleSumPairs(n, k, ar): count = 0 for i in range (n): for j in range(i+1,n): if ((ar[i]+ar[j]) % k) == 0: count += 1 return count

th_heuer + 0 comments Please see my comment below trying to explain this as simply as possible.

WolfEng + 7 comments For those wondering about a Java solution. The workings are pretty much the same as has been posted before in regards to an O(n) solution:

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[k]; int count = 0; for(int a_i=0; a_i < n; a_i++){ int number = in.nextInt(); number = number % k; int complement = number == 0 ? k : number; count += a[k-complement]; a[number] += 1; } System.out.println(count); }

Basically fetches the complement in the corresponding bucket adding to the result whatever is stored there. Then adds 1 to the bucket that corresponds to the remainder of the input.

Taking the provided example:

6 3 1 3 2 6 1 2 Input: 1 INITIAL STATE: Bucket[0]:0; Bucket[1]:0; Bucket[2]:0 Count:0 Remainder r: 1 Complement: 3 - r = 2 count+= Bucket[2]:0 bucket[1]++ Input: 3 INITIAL STATE: Bucket[0]:0; Bucket[1]:1; Bucket[2]:0 Count:0 Remainder r: 0 Complement: 3 - r = 3 -> 0 //(3 gets switched for 0 =) ). count+= bucket[0]:0 bucket[0]++ Input: 2 INITIAL STATE: Bucket[0]:1; Bucket[1]:1; Bucket[2]:0 Count:0 Remainder r: 2 Complement: 3 - r = 1 count+= bucket[1]:1 bucket[2]++ Input: 6 INITIAL STATE: Bucket[0]:1; Bucket[1]:1; Bucket[2]:1 Count:1 Remainder r: 0 Complement: 3 - r = 3 -> 0 count+= bucket[0]:1 bucket[0]++ Input: 1 INITIAL STATE: Bucket[0]:2; Bucket[1]:1; Bucket[2]:1 Count:2 Remainder r: 1 Complement: 3 - r = 2 count+= bucket[2]:1 bucket[1]++ Input: 2 INITIAL STATE: Bucket[0]:2; Bucket[1]:2; Bucket[2]:1 Count:3 Remainder r: 2 Complement: 3 - r = 1 count+= bucket[1]:2 bucket[2]++ FINAL STATE: Bucket[0]:2; Bucket[1]:2; Bucket[2]:2 Count:5

Hopefully I made no mistakes in the example run ;)

ronbeavers + 1 comment This is a really nice solution. I guess I was just hoping for a bit more clarity here. I see that you separate items into buckets and increment the count with the bucket. I'm curious though as to how this accurately gets number of items that are divisble evenly by k. Sorry if the question is basic, I haven't seen this done in this way before and I am attempting to re-learn algorithms.

WolfEng + 0 comments Uhm, let see, I'm guessing you're having trouble seeing how it manages to comply with the

`i < j`

rule. So, what does the rule really mean? It's only telling you that a value`a[i]`

should not be paired with itself, and a tuple`a[i],a[j]`

should not be considered twice so..`a[j],a[i]`

is not considered.

You can think of this solution of only running forward, so a number`a[i]`

appears always before a number`a[j]`

. As it runs forward, for each number it looks for previous occurrences of its complement (it looks for the i's for a particular j).

Say for instance if the divisor is 3, you could have this sequence:

1, 2, 1- The first is not matched with anything.
- The second is matched with the first. Although the 2nd could be matched with the 3rd, the algorithm isn't yet aware of the 3rd value...
- When the third value is read, it will be matched against the 2nd. Effectively matching the 2nd with the 3rd (remember
`a[i][j]`

and`a[j][i]`

should only be counted once ;)

I'm no algorithm guru, I had never seen this problem before... just started exercising for fun. But from my perspective there's no golden rule here, I don't see a generalization of this that's particularly valuable.

If the intention is learning, I would recommend you to focus your energy in understanding more generalized forms of algorithms... these here are mostly "quizes", perhaps try an algorithms book to find generalized sets of problems and solutions.

Also, many interesting real life problems are more about the data structures used and then the algorith comes natural to the data structure itself, so perhaps a focus on data structures is worth your while too...

Of course, these quizes have a "fun" element, and exercising can really help in making the learning stick, so you could do both :P... just get the basics strong and then go for the corresponding quizes I guess.

thaihocmap123 + 0 comments Do we have to sum them up first and then we mod them?

Please tell me why

KavinRanawella + 1 comment This solution is very nice. Because I got a longer piece of code. Good job.

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[n]; for(int a_i=0; a_i < n; a_i++){ a[a_i] = in.nextInt(); } int count=0; //checking aginst the condition for(int i=0;i<(n-1);i++){ for(int j=0;j<n;j++){ if(i<j){ if((a[i]+a[j])%k==0) count++; } } } System.out.println(count); } }

cys920622 + 1 comment Your i-loop terminates at

`< n-1`

but your j-loop terminates at`< n`

. Is there a possible Index out of bounds error there?Also you could save yourself a few iterations if every j-loop started at i+1. However this would not impact the O(n^2) time complexity.

KavinRanawella + 1 comment 1.No there is no any error. I just want to omit the situation where i=n and j=n. That's all.

2.That is a nice solution. Then u can directly skip the i>=j part. Thanks a lot.

btw, can u explain the part u said "this would not impact the O(n^2) time complexity" please?

cys920622 + 0 comments Sure. What I meant is that even if you skip all 'j' values less than or equal to 'i', you will still have an O(n^2) time algorithm. In practice it will be a bit faster because you are 'skipping' some iterations, but strictly in terms of time complexity / running time, it is still the same O(n^2) time.

joris_suppers + 0 comments Nice I got something similar :)

public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int k = in.nextInt(); int a[] = new int[k]; int count = 0; for(int i=0; i < n; i++){ int remainder = in.nextInt() % k; int complement = (remainder == 0) ? 0:k-remainder; count += a[complement]; a[remainder]++; } System.out.println(count); }

vivekwisdom + 0 comments Nice Explanation :)

daft_leech + 2 comments This is a way simpler solution with Java 8:

return IntStream.range(0,n).map(x -> IntStream.range(x+1,n).map(y -> (ar[x]+ar[y])%k==0?1:0).sum()).sum();

alpeshgediya + 1 comment Can you please explain logic

daft_leech + 0 comments Loop through the index of the array for x. Do the same for y for each x, but y is always greater then the current x. Check if the arrayvalues of the positions x and y as a sum is divisible by k. If true add 1 to the sum. Return the sum. All in one line.

raimund_klein + 0 comments Same idea, but using the Stream's

`count()`

method which I believe is more idiomatic:// Complete the divisibleSumPairs function below. static int divisibleSumPairs(int n, int k, final int[] ar) { return (int) IntStream.range(0, ar.length) .mapToLong(baseIndex -> Arrays.stream(ar, baseIndex + 1, ar.length) .filter(value -> (ar[baseIndex] + value) % k == 0) .count()) .sum(); }

sicter + 0 comments This confused me only because of the variable naming. I expected complement to be the bucket you need to check, when in actuality you must check k-complement. This assignment of complement made this solution make sense to me:

int complement = number == 0 ? 0 : k-number; count += a[complement];

RodneyShag + 5 comments ### Simple and efficient O(n+k) solution

From my HackerRank solutions which contains additional comments in code.

Runtime: O(n + k), by doing only 1 pass of the values

Space Complexity: O(k)We keep track of the mod values in buckets for each number we read. We can do this by creating k buckets where bucket

*i*counts each number*n*where n % k = i.Notice that each bucket has a corresponding

*complement*bucket. That is, if we take the mod value of one bucket and add it to the mod value of another bucket, we get*k*.Bucket Complement Bucket ------ ----------------- 0 0 1 k-1 2 k-2 3 k-3 ...... k-3 3 k-2 2 k-1 1

As we come across each number, we find its corresponding complement bucket. Each number in this complement bucket can be paired with our original number to create a sum divisible by

*k*static int divisibleSumPairs(int n, int k, int[] ar) { int [] bucket = new int[k]; int count = 0; for (int value : ar) { int modValue = value % k; count += bucket[(k - modValue) % k]; // adds # of elements in complement bucket bucket[modValue]++; // saves in bucket } return count; }

## Sample Bucket placement

For the following sample input

6 3 1 3 2 6 1 2

We have

Bucket Integers Count ------ -------- ----- 0 3, 6 2 1 1, 1 2 2 2, 2 2

EvanMJ + 1 comment Can someone please explain. I read the comment fully but I'm lost!

RodneyShag + 1 comment Hi. I added a detailed explanation to my original post to help clear up any confusion.

andromeda3107 + 1 comment Thank you for the great solution. I think you should mention the following property of modulus in your comment for more clarity:

(a+b)%n=(a%n+b%n)%n

RodneyShag + 1 comment Hmmm. That equation you put is correct. However, it complicates the logic for me a bit as it makes more sense to me as (a+b)%n.

bhawana053 + 1 comment how does your solution ensure i < j for every pair ?

RodneyShag + 1 comment The question asks to print pairs, for every i < j, where a_i + a_k is divisible by k. This constraint was placed in the problem so that we count pairs just once. For example, we want to count (a_i, a_j), but not also (a_j, a_i).

My solution counts each pair once. This is achieved by looping linearly through the input, and comparing each number to previous numbers only.

bhawana053 + 0 comments Thank you.

alfredooctavio + 1 comment Great job. I would like to ask you where you find this kind of logic? I saw that you have knowledge about algorithm efficiency. Can you suggest me some books that I can read, my code solution was good but yours is better. My best regards!

RodneyShag + 1 comment There are some tricks that are handy to know. I think this is called bucket sort and it's a good one to memorize, so you can apply to new problems in the future.

I think I came across this trick when learning about sorting algorithms (Such as QuickSort and MergeSort). Wikipedia might have some good summaries and pseudocode for various sorts.

alfredooctavio + 0 comments I really appreciate your comment. Thank you.

BitL0rd + 0 comments [deleted]nontuplet + 0 comments More efficient than problem setter's unromantic solution!

mike_buttery + 0 comments In python using dictionary as bucket

def divisibleSumPairs(n, k, ar): d = {} c = 0 for i in ar: key = i % k if (k - key) % k in d: c += len(d[(k - key) % k]) d.setdefault(key, []).append(i) return c

ShakeSaab + 7 comments Works fine in c++. Passes all tests.

`int n; int l; int count = 0; cin >> n >> l; vector<int> a(n); for(int i = 0;i < n;i++){ cin >> a[i]; } for(int i = 0;i < n;i++) { for(int k = i+1; k < n;k++) { if((a[i] + a[k]) % l == 0 && i < k) count++; } } cout << count;`

dhb2411 + 0 comments You do not need to check for (i < k) because k is initialised as i+1.

Ghost_dsb + 0 comments you can restrict i to n-2 (ie i < n-1)

jitendra21 + 0 comments int main(){ int n; int k; cin >> n >> k; vector a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; } int count = 0;

`for(int i = 0; i < n; ++i) { for(int j = i+1; j < n; ++j) { if((a[i] + a[j]) % k == 0) { ++count; } } } cout<<count; return 0;`

}

No need for i < k check

Sudarshan_P + 0 comments What is the need for (i

pkmuck33 + 3 comments This code will compile and run because c++ doesn't do bound checks on arrays. However you're accessing unknow memory in your code.

for(int i = 0;i < n;i++) { for(int k = i+1; k < n;k++) { /*a[k] access unknown memory when "i = n-1". undefined behavior. It just happen to work in this instance. **/ if((a[i] + a[k]) % l == 0 && i < k) count++; } }

vasukapil2196 + 0 comments [deleted]vasukapil2196 + 0 comments [deleted]rheasanjan + 0 comments Why doesnt this logic work in C? I tried the same but I didnt get the right output.

_MANU_ + 0 comments Not O(n) solution though......

RodneyShag + 0 comments Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

delight182 + 7 comments My O(n) C# solution:

static void Main(String[] args) { var nk = Console.ReadLine().Split(' ').Select(Int32.Parse) .ToArray(); int n = nk[0]; int k = nk[1]; var arr = Console.ReadLine().Split(' ').Select(Int32.Parse) .ToArray(); var count = 0; var counts = new int[k]; for (var i = 0; i < n; i++) { // the idea is that if (a1 + a2) % k == 0 // then (a1 % k + a2 % k) should be equal to k (or 0) var bucket = arr[i] % k; // adding all new combinations with arr[i] to the count // also handling bucket == 0 with % k here count += counts[(k - bucket) % k]; counts[bucket]++; } Console.WriteLine(count); }

naveenpragathesh + 1 comment Could you please explain this in detail? Mainly how we are finding the available pairs of given value in the above method

delight182 + 2 comments First of all, we need to notice that

`(A + B) % K = ([A/K] * K + A % K + [B/K] * K + B % K) % K = (A % K + B % K) % K`

(i.e. remainder of the sum equals to the remainder of the sum of the remainders). What it gives us is that in order to find B knowing A where`(A + B) % K`

it's enough just to look at`A % K`

and`B % K`

.Then, consider we are at some item

`A[j]`

right now and we need to calculate how many pairs this`A[j]`

makes with all the previous items`A[i], i < j`

. That is actually a number of items`A[i], i < j`

where`A[i] % K`

complements`A[j] % K`

. By "complements" here I mean that`(A[i] % K + A[j] % K) % K == 0`

. That actually means that they are either both == 0 or their sum == K.`(K - A[j] % K) % K`

effectively calculates this complement.Wrapping it up, we divide all the items in

`A`

into buckets by`A[i] % K`

value. This gives us the ability at each step to see how many pairs we have involving some item`A[i]`

. Iterating the array once and calculating only pairs on the left helps us not to count one pair two times while still covering all the combinations.Hope this helps.

naveenpragathesh + 0 comments Great explanation..Thanks a lot

rstormsf + 1 comment @delight182 Damn...I think I'm still confused about

`counts`

array and how those buckets workzhshqzyc + 0 comments It is same as

`int index = (k - bucket) % k; count = count + counts[index];`

and

`counts[bucket]= counts[bucket] + 1;`

thehoneymad + 0 comments This is definitely the best one here. The fact of actually getting the combination number by isolating each one of the input is absolutely brilliant.

mjdxn + 1 comment Despite the additional trick you've used, this solution's worst case runtime complexity is O(n+k), not O(n). The offender is this line:

`var counts = new int[k];`

C# has to initialize all k of those values to 0. While this may be fast on hardware, it still takes O(k) time in a standard model of computation.

You could attempt to replace this with something like a hashtable/dictionary, but then you lose O(1) lookup + possible insertion time for each input element. If m is the total number of mod buckets encountered and it takes O(log(m)) time to insert/lookup, then the worst case runtime with this hashtable would be O(n*log(m)). This may or may not be an improvement over O(n+k) depending on how m and k compare to each other. You could run both approaches concurrently for O(min(n+k, n*log(m))) worst case time.

Also keep in mind that the trick you are using here is effectively a trade-off in multiplications + a bitshift (for computing n'(n'-1)/2 for each bucket at the end) and distributing that computation via lookups and additions (over the n elements in the main loop). The multiplication approach will be faster at some point after where you exceed the word size of your architecture (after that point, we cannot assume that addition and multiplication are constant time operations).

delight182 + 1 comment Thanks for your valuable additions.

To be honest I've never thought about how array initialization adds the computational complexity to the algorithm as a whole. And have never seen this idea in the books I've read (I'd be glad if you could recommend some literature that covers it at this level). Nevertheless my algorithm is defininely an algorithm that needs the array to be initialized, so your point is completely valid.

The last point is completely valid too. It's just we had already had a multiplication version here, so I wanted to show more concise addition-only version.

As for hashtable, could you elaborate on why you say hashtable has O(log(m)) insert/lookup time? I always thought it's amortized O(1). Otherwise I aggree that if the number of encountered buckets is much less than K then Hashtable variant will be preferable.

mjdxn + 1 comment The array allocation complexity has to do with the internals of the language/compiler. For a language like C#, that allocation operation has to go through chunks of the memory and forcibly set each element of the array to 0. Other languages or operators might do this lazily by just marking the start and end points of allocated memory. This is constant time with random access, but you cannot guarantee that all the elements are 0 (they are instead garbage values that are left over from whatever was in that memory location previously). You might find more details about this in a computer architecture or compilers textbook.

Most hash table designs usually have a tradeoff between having constant worst case lookup and constant worst case insertion. Some designs do one or the other in constant worst case time while the other . I wrote "insertion/lookup" to encompass this. These tend to have a logarithmic worst case complexity for some operation, but also have an EXPECTED (not worst case) amortized constant runtime complexity (over uniformly random access sequences).

delight182 + 2 comments `you cannot guarantee that all the elements are 0`

True, I was referring to this when I said that my algorithm definitely requires that all the counts are 0 at the beginning of the cycle (because we'll have reads before any writes). So it's not about computer architecture or compilers at all, it's about the algorithm itself - I'll still have to manually nullify the memory in not-nullifying-by-default language. Luckily in C# newarr opcode really translates to appropriate machine code.

When I was referring to literature, I was saying that most common books/articles used for interview preparation will just skip array initializations when calculating time complexity, which I believe now is pretty superficial. I'd like to see a book that is not like that.

As for hashtables, now I see I didn't pay attention you were talking about worst time. Thanks.

mjdxn + 0 comments `it's not about computer architecture or compilers at all`

This is false. Both things significantly clarify what your algorithm is actually doing on the machine it is running on. It is equivalent to defining the model of computation that goes with your complexity measure. Some computations require more resources on some models of computation and fewer on others.

`not-nullifying-by-default language`

This property is enforced by the behavior of the C# compiler you are using. The fact that there is some gentleman's agreement to write all C# compilers the same way is irrelevant. Not all languages are lucky enough to have this. Some special architecture out there might allow you to zero out memory in constant time. A C# compiler could be modified to take advantage of this, which would allow your algorithm to truly be O(n) instead of O(n+k) without any edits.

`I'd like to see a book that is not like that.`

The interview prep materials I've seen are, indeed, all very hand wavey and superficial. I stand by my suggestion. Having additional knowledge of how your code works under the hood (i.e. what choices compilers make and how computation is done on your processor) will tell you exactly how complex (resource-wise) each operation is. I'm not aware of an alternative approach to get at what you want that does a better job of this.

askarovdaulet + 0 comments An interesting discussion. I actually agree with you at this point, that this is about the algorithm itself. The complexity will be O(n+k) here regardless of the language you use, unless you have some magical infinite memory all initialized with zero bits. Then you can do some simple arithmetic and allocate properly initialized memory instantly independent of the value of k.

Now, the actual constants hidden in the O(n+k)~alpha*n+beta*k, in particular beta will obviously depend on the language, compiler, operating system, etc... And in case of instantiation beta should be pretty small already.

Regarding lazy initialization, it will not be helpful here, since you rely on the values being zero on your first lookup. If one insists on lazy array, another boolean array of size k is needed to keep track of which entries of the integer array were already incremented/touched by the algorithm. But all entries of this boolean array of size k itself have to be initialized to false, the problem becomes circular. Seems like there is no way around the O(n+k) from the computer science perspective.

Regarding the general downsides of this algorithm, I think the space requirement is a much more serious issue. Consider this case n=2, k=2e10, a = [1,2]. A simple O(n^2) will solve this very quickly, while the bucket approach might stall on trying to create an array of integers of size k. So, it might be a good idea to first check the values of n and k and branch into two different approaches based on the value of k. This is what library sorting algorithms do frequently.

wibgyor + 0 comments [deleted]patelurvil38 + 0 comments count += counts[(k - bucket) % k]; counts[bucket]++;

What is this two lines mean?can you explain in brief?

JaroslavPernica + 0 comments I did O(n) in js using Maps. I iterate over numbers a and then calculate mod and complementary to the mod needed for the sum equal k. then i save complementary to hashmap and the value in the hashmap means how many numbers could make the pair. Since hashmap get and set are O(1) i assume i have O(n).

function divisiblesumpairs (n, k, a) { let compls = new Map(), count = 0; for (let i = 0; i < n; i++) { let m = a[i] % k, c = (k - m) % k, p, q; if (p = compls.get(m)) count += p; if (q = compls.get(c)) compls.set(c, ++q) else compls.set(c, 1) } return count; }

glukki + 0 comments Oh man, this solution is much better, but underrated! Reading of buckets explanation in more popular comments on top I had a feeling, that complexity can be reduced even more, and calculation made just with 1 loop. Thank you!

rahulrajpl + 0 comments For Python Lovers

def divisibleSumPairs(n, k, ar): # Complete this function count = 0 for i in range(n-1): j = i+1 while j < n: if ((ar[i] + ar[j]) % k) == 0: count += 1 j += 1 return count

NYJ1qCr + 2 comments Use Python 3:

n, k = list(map(int, input().split())) a = list(map(int, input().split())) b = [[c, d] for x, c in enumerate(a) for y, d in enumerate(a) if x < y and (c + d) % k == 0] print(len(b))

sowerk + 9 comments Slightly more pythonic:

`res = sum((i+j)%k == 0 for x, i in enumerate(a) for j in a[x+1:])`

Since True == 1

afif_benmati + 0 comments brilliant!

udaykumar_uk245 + 1 comment Can you explain me your Code.

asperatology + 1 comment `res`

is the result.`sum()`

sums up all of the elements that matches the condition,`(i+j)%k==0`

, and the elements are gathered from pair`(x,i)`

.`enumerate(a)`

returns multiple pairs,`(x, i)`

, where`x`

is the index of the element, and`i`

is the element value itself, for each element in the array`a`

. That also means`j`

is the element in the array`a`

where the index is`x+1`

or`to the right of a[x] by 1`

. In short,`i`

is`a[x]`

and`j`

is`a[x+1]`

.So, you have the array elements,

`i`

, and`j`

. Given that when iterating through the array`a`

, the`(i+j)%k==0`

then becomes something similar to the following sequence, due to`True`

being evaluated as`1`

:`0, 0, 1, 0, 0, 0, 1, 0, ...`

Which when calling on

`sum()`

, will give you the total count of those that satisfied the condition`(i+j)%k==0`

.`res = 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + ...`

udaykumar_uk245 + 0 comments Thank you

guptaayush241 + 0 comments Hats off man!

ameykulkarni + 0 comments Please change your name from sowerk to pythonKing

msambitkumar1991 + 1 comment Nice logic :)

udaykumar_uk245 + 0 comments Thank you

tadamori_yoshi + 1 comment I went slightly different way

n, k = list(map(int, input().split())) a = list(map(int, input().split())) print (sum([(a[i]+a[j])%k==0 for i in range (n) for j in range(i+1,n)]))

askarovdaulet + 0 comments You can forego list() call on the first line since you immediately proceed to multiple assignment without using any list-specific methods.

I also used range() in my solution since it's a generator in Python 3, which saves memory as opposed to slicing a[i+1:] which copies the references (8 bytes each) of the sliced portion of list. But in Python community this might be called premature optimization :)

askarovdaulet + 0 comments Very nice! A couple of things that I could suggest is changing the names of the variables for clarity, since people typically use i and j for indexing and x for the iterable values:

res = sum((ai+aj)%k==0 for i,ai in enumerate(a) for aj in a[i+1:])

Another optimization is using islice, which though slightly sacrificing readability improves the performance since slicing is not memory or time efficient in this case.

res = sum((ai+aj)%k==0 for i,ai in enumerate(a) for aj in islice(a,i+1,n))

mkhalil22 + 0 comments Smart solution!

atri_sid + 0 comments I did something similar, but without using enumerate: result = sum([(ar[i] + j)%k == 0 for i in range(n) for j in ar[i+1:]])

Do you think there is any performance difference between your logic and mine? Is it a good idea to use "enumerate" instead the way I have done?

PS - a beginner here.

RodneyShag + 0 comments Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

neldarov + 1 comment The main trouble with hackerrank problems is the way the problem is explained, poorly explained. It takes half an hour to get what it requires but 5 mins to code ((

CameronZup + 1 comment Agreed, I thought it wanted me to only count pairs that were divisable by k and when one was lower in value than the another because of the "i < j" part, I interpreted that as meaning when i is less than j and i+j % k ==0.

sayianin + 1 comment and it doesnt mean it?

zarrellab + 1 comment Easy to read python solution using itertools and list.count() method:

from itertools import combinations pairs = [sum(pair) % k for pair in combinations(a, 2)] print(pairs.count(0))

RodneyShag + 0 comments Nice job. Your solution is O(n^2). If you're interested in a challenge, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

kzliu + 2 comments python solution

print(sum([1 for i in range(n) for j in range(i) if (a[i]+a[j])%k==0]))

askarovdaulet + 0 comments Nice. It took me a few seconds to realize that range(i) can work here instead of range(i+1,n). You just look at all the same combinations in different order.

RodneyShag + 0 comments Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

Sort 803 Discussions, By:

Please Login in order to post a comment