You are given a list of n integers Design an algorithm that

You are given a list of n integers. Design an algorithm that returns the number of pairs of duplicates in this list. For example, if the list is (13,3,8,3,13,7,13,9,13), then the four 13\'s in list yield 6 pairs of duplicates and the two 3\'s in the list yield one pair. The other elements in the list are all unique. Thus your algorithm should return 7 as the total number of pairs of duplicates. Your algorithm should run asymptotically faster than the simple Psi(n^2) time algorithm that examines all pairs of elements in the list.

Solution

Algorithm:

1.    Sort the given list using merge sort.                            

                                                                                     – O (n log n)

2.    Declare the variables pair and totalPairs

                                                                                     -- O ( 1 )

3.    After sorting the duplicate numbers will be clubbed together. Iterate through the list and count the number of times each element appears. Store the frequency of each element in the variable value.

-- O ( n )

a.         Calculate the total number of possible pairs for the key integers having value greater or equal to 2.

                                          i.    Pairs = Value * (Value – 1) / 2

                                                             - O ( 1 )

b.         Add the above value to the totalPairs.

                                          i.    totalPairs = totalPairs + Pairs.

                                                            - O ( 1 )

c.          Repeat the steps 3 for all integers in the list    - O(n)

4.    Print the totalPairs. - O(1)

Overall Complexity is O (n log n)

Example:

List: {13, 3, 8, 3, 13, 7, 13, 9, 13}

Step1: Sort the list. The resultant list after sorting is : {3, 3, 7, 8, 9, 13, 13, 13, 13}

Step 3: Iterate through the list to find the frequency of each element.

            For the element 3, value = 2

a.        The key 3 has the value 2

                        Pairs = 2*(2-1)/2

                                 = 1

b.     totalPairs = 1

c. Repeat the step 3 for all distinct elements. The frequency of the elements 7,8, and 9 are 1.

Step 3: Iterate through the list to find the frequency of each element.

            For the element 13, value = 4

a.           The key 13 has the value 4

                        Pairs = 4*(4-1)/2

                                 = 6

b.           totalPairs = 6 + 1 = 7.

      Step 4: totalPairs = 7.