# Time efficient way to count pairs in an array whose sum is divisible by a specific number?

Given an array of integers, we want to find how many explicit pairs can be made such that their sum is divisible by 60. The pairs are not necessarily non-unique.

For example, let's say the input into our function ReturnPairCount() was as follows:

[29, 20, 30, 100, 30, 121, 160, 31, 20]

our function would return x because it found the following to be pairs whose sum add up to a number that is divisible by 60. Those pairs are:

(29, 31), (20, 100), (20, 160), (30, 30), (100, 20), (160, 20)

Note that (30, 30) is a pair because (array[2] + array[4]) % 60 == 0.

The obvious and immediate thing is to make a nested for loop

int ReturnPairCount(List<int> someNums)
{
for (int i = 0; i < pairs.Count - 1; i++)
{
for (int n = i + 1; n < pairs.Count; n++)
{
if ((pairs[i] + pairs[n]) % 60 == 0)
{
count++;
}
}
}
}


Can we improve the performance?

My initial though is to make a dictionary/hashmap - we could save on time by not counting pairs for duplicate integers. For example,

[1, 1, 1, 59]

We can see that we have three 1's, and that each will make a pair with 59. We could catalog this in some way with a <key, value> of <integer, count> where integer is 1 and count is 3. I am unsure how to iterate through that in a performant way, which is equal to a divergent series of (n-1)(n)/2 = (4-1)(4)/2 = 6.

• Can you please be more specific? Do you want to count duplicates or do you not want to count duplicates? That means, if an additional 30 was added to your list, would you expect the count to be increased by 2 for both combinations with the other two 30s? Sep 25, 2020 at 5:33
• Sep 25, 2020 at 6:15
• @DocBrown This isn't homework. I think Ive earned enough reputation and been on this site long enough to deserve a minimum amount of credibility that I don't come here looking for homework to be solved for me - if I even had any. I find your insinuation insulting and unnecessary. Sep 25, 2020 at 22:28
• If this is not a homework, then could you please explain what is the real life problem you're dealing with. This problem looks a lot like homework for introductory or intermediate level course of algorithms. It's not an insult to point it out. Sep 28, 2020 at 9:47
• @COMEFROM Since when did explaining where questions are derived from become a part of the SE process? Sep 28, 2020 at 16:16

Solution in O(N) time and O(N) space using hash map.

## The concept is as follows:

If (a+b)%k=0 where

a=k*SOME_CONSTANT_1+REMAINDER_1

b=k*SOME_CONSTANT_2+REMAINDER_2

then (REMAINDER_1 +REMAINDER_2 )%k will surely be 0


so for an array (4,2,3,31,14,16,8) and k =5 if you have some information like below , you can figure out which all pairs sum %k =0

Note that, Bottom most row consist of all the remainders from 0 to k-1 and all the numbers corresponding to it. Now all you need to do is move both the pointer towards each other until they meet. If both the pointers locations have number associated with it their sum%k will be 0

To solve it, you can keep track of all the remainder you have seen so far by using hash table

1. create a hash map Map<Integer, List>.
2. Pre-populate its keys with 0 to k-1;
3. iterate over array and put remainder of each number in the map with Key = remainder and put the actual number in the list,
4. Iterate over the key set using two pointers moving each other. And sum += listSizeAsPointedByPointer1 * listSizeAsPointedByPointer2
• This is most likely a homework. Writing full answers for homework problems is counter-productive. Besides, creating lists and building a map is unneccessary for counting occurrences. A hash map is quite inefficient here. An array of 60 integers works better. Sep 28, 2020 at 9:29
• @COMEFROM It was from a time when I was practicing Leetcode problems. Finished college years ago. There are a lot of people out there practicing algorithms to improve their careers. Apr 3, 2022 at 1:42

What counts is x modulo 60. There are only 60 different values. Count how often each value happens. If you have n values equal to 14 modulo 60 and m elements equal to 46 modulo 60 that gives you nxm pairs. Now figure out how to handle 0 modulo 60 and 30 modulo 60.

Given n integers, produce pairs which sum to a number evenly divisible by d.

Contrary to the earlier comment, this is the same problem as pairs which add up to d. (Extras credit: prove that this is so).

The straight forward nested loop solution is O(n**2) in every case.

Any solution will be O(n**2), because we’ll always have to produce the pairs, and the number of pairs to be produced can be anywhere between 0 and n ** 2, depending entirely on the distribution of values in the data.

What we’re looking for is a solution that takes advantage of the distribution whenever it can, so that when a particular distribution produces far fewer than the maximum number of pairs, we do far less than the maximum amount of work.

Sounds an awful lot like a homework problem.

The best I can do is to comment on the proposed solution of using a dictionary. You could use a dictionary. You might also consider a close cousin-the thesaurus. You could also use an array of arrays. You will need to know what to use them for.

• "Any solution will be O(n**2), because we’ll always have to produce the pairs" That's true. However, the quoted problem does not say you have to produce the pairs. If producing the count of pairs is enough, then it's O(n). Sep 25, 2020 at 7:50
• True dat. Good catch. The title says "find pairs", whereas the body says "count pairs". Sep 25, 2020 at 9:07

This smells like homework, so I'm not going to give a full answer. A couple of tips should do.

1. The number of additions (a + b) needed to solve the problem does not depend on the value of N.
2. One pass is enough. The complexity is O(n).
3. You're dealing with a quotient ring. There are only 60 unique numbers in it.

It's very important to notice that you don't have to produce the pairs to solve the problem:

we want to find how many explicit pairs

Finding out how many pairs there are is O(n). Listing all pairs is O(n^2).