You are given a list of n integers. Design an algorithm that returns the number

Question

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

Explanation / Answer

Algorithm to examines all pairs of duplicate elements in the list:

1) Create a empty hashMap(Which will take interger as key and frequency of that interger in the list as value)- O(1)
2) Iterate throgh the list and check if integer is found in the list
   if found: increase value of that key(increase the occurence)
   if not found: add that interger as key and '1' as value
  
This entire step will take O(n)(i.e., size of the list)
3) Create totalPairs variable - O(1)
4) Iterate throgh the hashMap and

   4a)calculate the number of possible pairs using below formula for the integer which has frequency greater than 2(indicates duplicate value in the list):

       no.of possible pairs = Value*(Value-1)/2 - O(1)
   4b) add above value to the totalPair possible variable - O(1)
   4c) Repeat setp 4a and 4b for the all the integer in the hashMap. - O(n)
5) Print the totalPairs - O(1)

Overall complexity - O(n)

Example for the above example:

list: (13,3,8,3,13,7,13,9,13)
Step1: {}
Step2: hashMap{"key->value"}
   {"13->1"}
   {"13->1","3->1"}
   {"13->1","3->1","8->1"}
   {"13->1","3->2","8->1"}
   {"13->2","3->2","8->1"}
   {"13->2","3->2","8->1","7->1"}
   {"13->3","3->2","8->1","7->1"}
   {"13->3","3->2","8->1","7->1","9->1"}
   {"13->4","3->2","8->1","7->1","9->1"}
Step3: totalPairs = 0
Step 4:

Step4a:   "13-4"
   no.of possible pairs = 4*(4-1)/2 = 6
step4b : totalPairs = 6
Step4a:   "3-2"
   no.of possible pairs = 2*(2-1)/2 = 1
step4b : totalPairs = 7

Note: for 8,7,9 Step4 will be skipped because frequency is not greater than 2

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.