algorithms – Time efficient way to find pairs in an array whose sum equals 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 do not need to be non-unique.

For example (29, 20, 30, 100, 30, 121, 160, 31, 20) has 6 pairs -> (29, 31) (20, 100) (20, 160) (30, 30) (100, 20) (160, 20)

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

 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++;
                    }
            }
    }

but that’s too slow. The above also doesn’t factor in duplicates like if the array had the number “30” as four elements, which is equal to a divergent series of (n-1)(n)/2 = (4-1)(4)/2 = 6.

How can we improve the performance?

My initial though is to make a dictionary/hashmap, but I am unsure how to iterate through that in a performant way.