Moderator: I shall give 2 easy test cases first, and then crush their hopes with the rest of them.

For anyone who is having issues with the running time: i had the same when i used factorial to compute (n choose 2).

Rather than using factorial you can use a simple formula: n * (n - 1) which is equal to (n choose 2).

K for whomever that only had 3 cases passed, pay attention to 32 bit vs 64 bit representation. And what's tricky about this is declaring 64 bit representation and assigning it with 32bit X 32bit is screwed up too(In Java). Thanks to whoever made up this question, this is 30 mininutes of my life I am not getting back.

How is this challenge related to sorting?

I solved it by counting the number (N) of times an integer occurs in the array (one traversal, no need for sorting), then summing 2*nCr(N, 2) for N >= 2.

Can sorting improve the algorithm?

Of all the challenges I've done, I liked this a lot. Just apply what you've learned during the past sorts (counting and etc) and simple arithmetic. :) Got the logic in 10 minutes but there were still runtime errors due to wrong data types being used.