Check if a list has exclusively duplicate elements (i.e., no unique elements)

user_12276989 0
Viewed 52

I have an array with an even number of ints and want to check if all of those elements are 'paired', ie [0, 1, 0, 1] has a pair of 1s and a pair of 0s vs [0, 1, 1, 2] has only one 0 and one 2.

My first thought was to cast it to a set and check if the set had a length of half of the original:

def isPaired(arr):
    return len(arr) / 2 == len(set(arr)

But that's incorrect if the arr is [0, 1, 0, 0].

my next thought was to sort the array, and compare each even-numbered index with the next index:

def isPaired(arr):
    arr.sort
    for i in range(0, len(arr) - 1):
        if i % 2 == 0 && arr[i] != arr[i+1]:
            return False
    return True

This works, but the runtime is at least the runtime of the sort. Is there a solution to this problem without sorting the array?

list python
3 Answers

You can use a Counter like this:

from collections import Counter
all(c % 2 == 0 for c in Counter([0, 1, 0, 1]).values())
# True

You can also sort and then compare consecutive elements:

l = sorted([0, 1, 0, 1])
all(x == y for x, y in zip(l[::2], l[1::2]))
# True

Complexity wise, prefer the first option since its worst case complexity is only linear.

user_49090870

This uses less memory:

INPUT = [0, 1, 0 , 1]

odd = set()
for n in INPUT:
    if n in odd: 
        odd.remove(n)
    else:
        odd.add(n)

print(not odd)

It accepts [1,1,1,1] as two pairs.

user_53788160 
def have_pairs(a):
    temp_dict = dict()
    for i in a:
        if i in temp_dict:
            temp_dict[i] += 1
        else:
            temp_dict[i] = 1
    frequency = temp_dict.values()
    pairs = True
    for i in frequency:
        if i % 2 == 1:
            pairs = False
            break
    return pairs


a = [1, 1, 2, 3, 3, 2]
print(have_pairs(a))
# True

a = [1, 1, 2, 3, 3]
print(have_pairs(a))
# False
user_35799550
Related