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.

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.

My answer is pretty simple. I've put all values on a map in C++ and just added the values n*(n-1).

Solution:

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int a, b, ans=0;
        cin >> a;
        int arr[a];
        map<int, int> mp;
        for(int i=0; i<a; i++){
            cin >> b;
            mp[b] += 1;
        }
        for(map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            ans += itr->second * (itr->second-1);
        cout << ans << endl;
    }
    return 0;
}

C++ coders , don't forget to use long long int

Hey folks, I can't quite understand why this is a combinatorics problem or why people are having issues with execution times.

My submission just goes over an array and saves how many occurrences of each number exists to a map. Then for each number that occurs more than once, I add n*(n-1) to the result and print it.

Am I doing this inefficient? The time complexity of this is basically just O(N) as I go over the array values once and the map values once and the storage complexity also is O(N) as the map can get at most N elements.

what will be the anwer for input 1 1 1 and for input 1 1 1 1