Sort 124 Discussions, By:
Please Login in order to post a comment
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?