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 ominus (n^2) time algorithm that examines all pairs of elements in the list.

Solution

Fact(n) // n is integer
   result = 1
   for i 1 to n
       result = result*i
   return result

FindDuplicatePairs(A) // A is the array
   intialize count array to 0
   for i 0 to A.length
       for j 0 to dup.length
           if dup[j] = A[i]
               count[j]++
           else
               dup[j++] = A[i]
               count[j] = 1

   for i 0 to count.length
       if(count/2 > 0)
           result = result+ fact(count/2)
   return result