CODEWITHSUNDEEP
pythonlist
jst
jst

Reputation: 33

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

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?

Upvotes: 3

Views: 59

Answers (3)

VPfB
VPfB

Reputation: 17267

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.

Upvotes: 1

newbie
newbie

Reputation: 1412

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

Upvotes: 0

cs95
cs95

Reputation: 402523

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.

Upvotes: 4

Related Questions