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?

Only 3 cases are passing. Can anyone check my code and help me with a hint if possible?
Thanks.