# Sherlock and Pairs

# Sherlock and Pairs

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

lk00100100 + 0 comments Don't forget to use double for the total. The answer gets really big.

ReallyBigInt * ReallyBigInt = TruncatedInt

((Double)ReallyBigInt) * ReallyBigInt = Double

mennanov + 4 comments 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).

bhgupta + 0 comments very nice tip Thanks!

Saeed96 + 0 comments thanks...this helped

Sid_S + 1 comment Actually, n choose 2 = n(n-1)/2

Saeed96 + 2 comments ya but n*(n-1)/2 wont work..cause we are choosing(0,1) as well as (1,0)..ifwe do n(n-1)/2 we will be choosing only one of them

Sid_S + 0 comments I do realize that. I was just pointing out that the formula given does not do what it was claimed to do.

n choose k gives you the number of combinations, but what you should be looking for here is the number of permutations. That happens to be n!/(n-k)! which in the case at hand is n(n-1)

shubham_marathia + 1 comment Actually we will be having two pairs from two indexes. So , we will take 2*(n-1)*(n)/2 .

zengruiwang + 0 comments It's actually permutation not composition, so P(n,2) = n * (n-1), C(n,2) = n * (n-1) / 2

JsNormandy + 2 comments 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.

HaabyHings + 0 comments thanks. helped me.

dvirtz + 0 comments +1

Thanks,

bahrim + 1 comment 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?

aaoferreira + 0 comments It uses the principles of counting sort https://en.wikipedia.org/wiki/Counting_sort

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

Thanks.phillm6 + 2 comments If you post a link to your code, I'll look at it

sahildua2305 + 2 comments phillm6 + 1 comment Well, I took a look at your code, and it does look like your algorithm is transparently correct. However, I submitted in Python, so I wonder if this is an issue with dealing with the unreasonably large numbers. Unfortunately, I'm not a C expert, so maybe someone who is could answer that. Maybe try rewriting in another language and see if your algorithm pans out there (mine was slightly different, but I don't think in any significant way).

Sorry I wasn't able to identify the issue, and good luck resolving it.

vidushig2 + 1 comment https://www.hackerrank.com/challenges/sherlock-and-pairs/submissions/code/16753889

please check my code too

thanks

tihom0k + 2 comments @vidushig2 your algorithm's time complexity in n^2 while it can be done in nlogn. Besides "int" is not large enough to hold 10^6 . Use long long int to be on safe side.

jaysolanki789 + 1 comment how is this possible with nlogn complexity?

Dhananjayrb + 1 comment yout can solve it at lesser complexity..here is my code,hope it helps. https://www.hackerrank.com/challenges/sherlock-and-pairs/submissions/code/17852526

samking123 + 1 comment can u plse send the code to ...samking321@yahoo.com

padalkars + 0 comments Please find the code below. Test cases passed 1,2 and 16 are passing. Rest all are failing.

`c int main(){ int t; scanf("%d",&t); while(t--){ long long int result = 0; long int n; scanf("%ld",&n);

long long int temp[100000] = {0}; for(long int x=0;x long long int te; scanf("%lld",&te); temp[te]++; } for(long long int j=0;j<100000;j++){ if(temp[j]>1) result += temp[j]*(temp[j]-1);`} printf("%lld\n",result); }`

return 0; } `

vijay008 + 0 comments It can be done in O(n). (My submission is nlogn.) Later I optimized my code.

FilipeGoncalves + 2 comments My algorithm is the same as yours. Did it in C++ though. I was failing the exact same testcases with Wrong Answer. Turns out it was due to integer overflow. My advice: don't use a plain int for

`count`

. Use`long long`

or`unsigned long long`

. Think about the extreme case where`N`

is 10^5 and every`A[i]`

holds the same number.`count`

will overflow.sahildua2305 + 1 comment Thanks, FilipeGoncaves!

Got AC now. But why should that be the error? I was just counting the number of same consecutive numbers, which will never exceed`10^5`

. The ans, I was storing in variable`ans`

itself, which was already a`long long`

. Can you explain a bit? :)FilipeGoncalves + 5 comments Yeah, I wasn't very clear, sorry. In fact,

`count`

itself doesn't overflow, but the result of`count*(count-1)`

does. Since`count`

is an`int`

, the multiplication is performed using`int`

, and the result is an`int`

, which only then is converted to`long long`

and assigned to`ans`

. By that time, it has already overflowed. Eg. if`count`

is 10^5,`count^2`

is going to be`10^10`

, a value that is typically too large for a plain`int`

. Always be careful when multiplication is involved - it is very easy to overflow, because in the general case, if you are multiplying 2 numbers that use`n`

bits, the result can have`2n`

bits. For example, 16 uses 4 bits (`1000`

). If you square it, you get 256 (`100000000`

) - 9 bits in the result. In your case, assuming 32-bit ints and using 2's complement, you can use at most 31 bits to represent a positive value, and as such, any value of`count`

that uses more than 16 bits*will*overflow. This means your code overflows every time`count >= 2^16`

, which is 65536. So, as you see, it overflows even for relatively small values of`count`

, that's why you failed so many tests. Hah... multiplication is so evil! Conclusion: always be careful with overflow when you're doing multiplication, it's very easy to blow it.deepesh23 + 0 comments thnks for the explaination buddy! i got all from 3... high5!

garuda_alpha + 0 comments Thank you so much for such a thorough explanation, greatly appreciated.

rahulhacker + 0 comments thank you FilipeGoncalves this explanation was really helpful :)

f2011035g + 0 comments Explanation was very nice and clear...Thankks

Dhananjayrb + 0 comments Thanks a lot for your wonderful explaination.Greatly appreciated.

vijay008 + 0 comments just long int will do the job.

padalkars + 0 comments I am facing a problem related to run time error. I have used long, and n(n-1) to calculate the final output. My code is in python. Here is the link to my code. Please have a look at it.

Thanks and regards.

goelakshay103 + 1 comment help me for the same

FilipeGoncalves + 1 comment Have you seen my reply about overflow?

goelakshay103 + 1 comment yes i have use long int also,still facing the same issue

fflewddur + 0 comments [deleted]

mportugal + 1 comment 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.

vidushig2 + 0 comments please explain how to solve this in simple terms.i have passes three test cases. https://www.hackerrank.com/challenges/sherlock-and-pairs/submissions/code/16753889

this is the link

smurfedasder + 0 comments 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; }

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

ahmetb + 1 comment 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.kilicars + 0 comments It is a combinatorics problem because we choose 2 from every repeating number group count and here also order is taken into consideration so it is P(k, 2) which is equal to k*(k-1) when simplified (k:repeating number group count).

I did the same thing and I think it is efficient. We cannot decrease it under O(n) because we have to read the array at least..

JM_praveenraj + 1 comment what will be the anwer for input 1 1 1 and for input 1 1 1 1

nahskia + 1 comment 6 for 1 1 1 and 12 for 1 1 1 1

JM_praveenraj + 1 comment thanks a lot

Sort 109 Discussions, By:

Please Login in order to post a comment