Instructions on codewars:

There is an array with some numbers. All numbers are equal except for one. Try to find it!

find_uniq([ 1, 1, 1, 2, 1, 1 ]) == 2 find_uniq([ 0, 0, 0.55, 0, 0 ]) == 0.55 It’s guaranteed that array contains at least 3 numbers.

The tests contain some very huge arrays, so think about performance.

This is the code I wrote:

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

It works as it follows: For every character in the array, if that character appears only once, it returns said character and exits the code. If the character appears more than once, it does nothing When attempting the code on codewars, I get the following error:

STDERR Execution Timed Out (12000 ms)

I am a beginner so I have no idea how to further optimize the code in order for it to not time out

The first version of my code looked like this:

def find_uniq(arr):
    arr.sort()
    rep = str(arr)
    for character in arr:
        cantidad = arr.count(character)
        if cantidad > 1:
            rep = rep.replace(str(character), "")
    rep = rep.replace("[", "")
    rep = rep.replace("]", "")
    rep = rep.replace(",", "")
    rep = rep.replace(" ", "")
    rep = float(rep)
    n = rep
    return n

After getting timed out, I assumed it was due to the repetitive replace functions and the fact that the code had to go through every element even if it had already found the correct one, since the code was deleting the incorrect ones, instead of just returning the correct one

After some iterations that I didn't save we got to the current code, that checks if the character is only once in the array, returns that and exits

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

I have no clue how to further optimize this

CodePudding user response：

You can use a dict or collections.Counter to get the frequency of each element with linear time complexity. Then return the element with a frequency of one.

def find_uniq(l):
    from collections import Counter
    return Counter(l).most_common()[-1][0]

CodePudding user response：

.count() iterates over the entire array every time that you call it. If your array has n elements, it will iterate over the array n times, which is quite slow.

You can use collections.Counter as Unmitigated suggests, but if you're not familiar with the module, it might seem overkill for this problem. Since in this case you know that there's only two unique elements in the array, you can get all of the unique elements using set(), and then check the frequency of each unique element:

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

CodePudding user response：

Compare the first two numbers. If they match, find the one in the array that doesn't match (longest solution). Otherwise, return the one that doesn't match the third. Coded:

def find_uniq(arr):
    if arr[0]==arr[1]:
        target=arr[0]
        for i in range(2,len(arr)):
            if arr[i] != target:
                return arr[i]
    else:
        if arr[0]==arr[2]:
            return arr[1]
        else:
            return arr[0]
    

CodePudding user response：

In your original code:

def find_uniq(arr):
    for n in arr:
        if arr.count(n) == 1:
            return n
            exit()  # note: this line does nothing because you already returned

you're calling arr.count once for each element in the array (assuming the worst case scenario where the unique element is at the very end). Each call to arr.count(n) scans through the entire array counting up n -- so you're iterating over the entire array of N elements N times, which makes this O(N^2) -- very slow if N is big!

The second version of your code has the same problem, but it adds a huge amount of extra complexity by turning the list into a string and then trying to parse the string -- don't do that!

The way to make this fast is to iterate over the entire list once and keep track of the count of each item as you go. This is easiest to do with the built in collections.Counter class:

from collections import Counter

def find_uniq(arr):
    return next(i for i, c in Counter(arr).items() if c == 1)

Given the constraint that there are only two different values in the array and exactly one of them is unique, you can make this more efficient (such that you don't even need to iterate over the entire array in all cases) by breaking it into two possibilities: either the first two items are identical and you just need to look for the item that's not equal to those, or they're different and you just need to return the one that's not equal to the third.

def find_uniq(arr):
    if arr[0] == arr[1]:
        # First two items are the same, iterate through
        # the rest of the array to find the unique one.
        return next(i for i in arr if i != arr[0])
    # Otherwise, either arr[0] or arr[1] is unique.
    return arr[0] if arr[1] == arr[2] else arr[1]

In this approach, you only ever need to iterate through the array as far as the unique item (or exactly one item past it in the case where it's one of the first two items). In the specific case where the unique item is toward the start of a very long array, this will be much faster than an approach that iterates over the entire array no matter what. In the worst case scenario, you will still have only a single iteration.