0

I'm doing a Codewars challenge for finding the unique value in a list and I'm having trouble finding the good way to do this process at my skill level.

This solution works for tests but times out the attempt (12000ms).

def find_uniq(arr):
    for element in arr:
        if arr.count(element) == 1:
            return element

link to the exercise: https://www.codewars.com/kata/585d7d5adb20cf33cb000235/train/python

4

3 Answers 3

1

Your algorithm is O(n^2) where n is the number of elements of your array. You should consider use a dict or collections.Counter.

# Not tested
def findUnique(arr):
  from collections import Counter
  counter = Counter(arr)
  for value, count in counter.items():
    if count == 1:
      return value
1

An easy way is to keep track of the counts of each item.

from collections import Counter

def find_uniq(arr):
    # Count each item.
    # I suggest you try to write your own Counter as an exercise.
    # You will need to loop over the entire array.
    # Store your results in a dict.
    counts = Counter(arr)

    # Now, loop over the resulting counts and check which item has a count of 1.
    for value, count in counts.items():
        if count == 1:
            return value

    raise ValueError("Could not find unique item!")
1

Solution based on sorting and checking of neighboring elements

def find_uniq(arr: list):
    arr.sort()
    n = len(arr) - 1
    for i, x in enumerate(arr):
        if (i == n or x != arr[i + 1]) and (
                i == 0 or x != arr[i - 1]):  # if there are no identical neighboring elements
            return x
    return None

print(find_uniq([10, 10, 10, 1, 1, 1, 1, 1, 100, 2, 2, 2, 2, 3, 3, 3, 3, 7, 7, 7, 7, 8, 8, 8, 8]))

Prints:

100
1
  • This worked, i thought my modified code would work, but it also times out. time to take some more classes thanks Commented Aug 28, 2021 at 3:56

Not the answer you're looking for? Browse other questions tagged or ask your own question.