3
$\begingroup$

Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array $a=[2,5,1,2,5,1,1,6]$ the pairs are $(2,2), (1,1), (1,1), (1,1)$ and $(5,5)$, so the function should return $5$. The solution needs to run in $O(n \log n)$ time and $O(n)$ space.

My algorithm first sorts the array using quick sort in $O(n \log n)$ time, then go through the sorted array and for each chunk of equal elements, keep track of the size of the group(which resets to $1$ when a distinct element is next), runs in $O(n)$ time.

If the next element equal the previous element, then increase the group size variable.

Otherwise, if the group size variable is bigger than $1$, add $n \choose 2$, where $n$ is the group size, to the overall sum of pairs variable(initially $0$), then reset the group size variable to $1$.

The problem I have is that, although the algorithm is correct, the algorithm runs in $O(n^2)$, which I think is because of the $n \choose k$ method.

The pseudo-code for my $n \choose k$ method is:

int binomial(n,k)
    if(k>(n-k)) k=n-k

    int b=1
    for(int i=0, m=n; i<=k; i++, m--)
        b=b*m/i

    return b

If the method does run in $O(n^2)$, then can I modify it to make it $O(n \log n)$. If its not possible to make a binomial coefficient method to run faster than $O(n^2)$, then does anyone have another algorithm for achieving the number of pairs from the array.

$\endgroup$
  • 1
    $\begingroup$ The binomial method seems incorrect since it tries to divide by $0$. However, its running time is $O(nk)$ which for $k=2$ would be $O(n)$ - a much tighter bound than $O(n^2)$. $\endgroup$ – Tom van der Zanden Dec 16 '15 at 19:32
  • $\begingroup$ ah I see, just out of curiosity, is it possible to answer the question without using a binomial coefficient. $\endgroup$ – Andrew Brick Dec 16 '15 at 19:35
  • 3
    $\begingroup$ Well, the number of pairs of $n$ elements is just $\frac{n\cdot (n-1)}{2}$ but I'm not sure if that counts as "not using binomial coefficients". $\endgroup$ – Tom van der Zanden Dec 16 '15 at 19:35
  • $\begingroup$ You say you think your algorithm runs in $O(n^2)$ time -- can you elaborate on why you think that? I suggest you try to work out the running time analysis in more detail, justifying every step, and taking into account the helpful comment from Tom van der Zanden. Once you've done that, I suggest that you either (a) answer your own question, or (b) edit the question to show your more detailed running time analysis and ask a specific question about what you remain uncertain about. $\endgroup$ – D.W. Dec 17 '15 at 1:08
3
$\begingroup$

Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.


Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.