CODEWITHSUNDEEP
pythonalgorithmperformanceiterationbig-o
JamalCrawford..
JamalCrawford..

Reputation: 187

Efficiently find number of pairs of duplicates

I am trying to find an algorithm that returns the number of pairs of duplicates in a list.

Example: Input: [13,4,8,4,13,7,13,9,13] Output: 7 (4 13's comes out to 6 pairs and two 4's comes out to 1 pair )

Can my algorithm become more efficient? I would like it to be faster than Theta(n^2)

Here is what I have:

my_List=[13,3,8,3,13,7,13,9,13]

pairs=0
alreadySeen=[]

for element in my_List:
  howMany=0
  if element in alreadySeen:
    False
   else:
    howMany=my_List.count(element)
    pairs=pairs+((howMany*(howMany-1))/2)
    howMany=0
    alreadySeen.append(element)

print(pairs)

Upvotes: 2

Views: 2130

Answers (5)

cool
cool

Reputation: 385

Time Complexity : O(N)

arr = list(map(int,input().split()))
    d = {}
    for i in range(len(arr)):
        if arr[i] in d.keys():
            d[arr[i]] += 1
        else:
            d[arr[i]] = 1
    ans = 0
    for val in d.values():
        if val > 1:
            ans += val*(val-1)//2
    print(ans)

Upvotes: 0

gkedia
gkedia

Reputation: 1

Here is a simple and efficient way of finding all possible duplicate pairs in a list with time complexity ~ O(N).

l = [13,3,8,3,13,7,13,9,13]
# Two pairs of 13 and One pair of 3
# Sum equals to Three
alreadySeen = []
total_no_of_pairs = 0
for i in range(len(l)):
    if l[i] not in alreadySeen:
        alreadySeen.append(l[i])
    else:
        # If element l[i] is present in alreadySeen list
        # Indicates a Pair and increments count
        # Remove element for creating a new pair
        total_no_of_pairs +=1
        alreadySeen.remove(l[i])

print(total_no_of_pairs)

Output:

3

Upvotes: 0

niemmi
niemmi

Reputation: 17263

@Hesham Attia already provided the correct algorithm, here's simple implementation with Counter:

>>> from collections import Counter
>>> l = [13,4,8,4,13,7,13,9,13]
>>> sum(x * (x - 1) // 2 for x in Counter(l).values())
7

Upvotes: 2

Hesham Attia
Hesham Attia

Reputation: 977

Here is an algorithm that runs in O(N).

  1. Iterate over the elements once to create a dict of each element and its count. The output of this step for your example is {13: 4, 4:2, 8:1, ...}
  2. Iterate over that dict and calculate the number of pairs for each element. The number of pairs for each element can be thought of as selecting 2 items from a list of N elements. This could be done by calculating the combinations without repetitions using the formula (N * (N-1)) / 2. So for 4 elements, there are (4 * 3) / 2 = 6 pairs.

Upvotes: 3

Mitesh Pant
Mitesh Pant

Reputation: 542

Here is a javascript code, you can convert this to phython code, the complexity is linear ~ O(n)

var arr = [13,3,8,3,13,7,13,9,13];
var count = {};
var totalpairs =0;
for(var i=0;i<arr.length;i++){
  if(count[arr[i]]){
    count[arr[i]]++;
  }else{
    count[arr[i]] =1;
  }
}

for(key in count){
  if(count[key] %2 == 0){
    totalpairs = totalpairs + count[key]/2;
  }
}

console.log(' total pairs are '+ totalpairs);

Upvotes: 0

Related Questions