# Divisible Sum Pairs

# Divisible Sum Pairs

usinha02 + 54 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 + 22 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.

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

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

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).

WolfEng + 8 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 + 2 comments 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 + 2 comments 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?

shivspm54 + 0 comments i also have same kind of logic. i think threre will not be any confusion now.

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

kotnalakotnala7 + 0 comments `function divisibleSumPairs(n, k, ar) { let count = 0; for(let i=0; i< n-1 ; i++) { for(let j=i+1 ; j< n ; j++){ if((((ar[i]+ar[j]) % k) === 0)) { count++; } } } return count; }`

RodneyShag + 6 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

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]

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

neldarov + 2 comments 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.

dorcamelda + 0 comments Unsure which firm produces Legitimate Coursework Writing Services in the academic writing industry to solve your Coursework Assignment Services? Legitimate Custom Coursework Writing Company is there to solve your problem.

Sort 1140 Discussions, By:

Please Login in order to post a comment