single element in a list

user_10363596 0
Viewed 580

I am fairly new to python and I came upon this code to find a single element in a list

Here is the code:

def single_number(arr):
    ones, twos = 0, 0
    for x in arr:
        ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
    assert twos == 0
    return ones
arr1 = [5, 3, 4, 3, 5, 5, 3]
print(single_number(arr1))

I just can't seem to understand what the line is doing

ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x)
assert twos==0
bit-manipulation python-3.x python
2 Answers

The purpose of that line is to implement an operation that returns the original value if applied three times with the input, and retains the input if applied once.

It's easier to understand if we wanted to pick a single value from an array containing pairs instead of triples. Then we could just do...

ones = ones ^ x

... because y ^ x ^ x == y. So all the pairs cancel out and you're left with the single value.

As others have commented, the three-item case is a pretty nasty obscure hack that should only be used when performance is essential and the problem is very specific.

I think the assert is just an attempt to confirm that the precondition was met, i.e. all numbers are triples except for one. It's not fail-safe.

user_446150

You would not want to do it like this, unless you are really memory-space limited - and even then, you probably should not use it.

This is some kind of bit shifting / bit ops "magic" that is

  • not intuitive
  • dangerous to fiddle with
  • bad to maintain
  • difficult to understand

Counter works in O(n) - thats about the best you can do to check all elements in a list - it just takes some more constant time (to setup the Counter object) and some space (to maintain inner dict) over this bit-shift thingy you found.

def getSingle(arr):
    from collections import Counter
    c = Counter(arr)

    return c.most_common()[-1]  # return the least common one -> (key,amounts) tuple

arr1 = [5, 3, 4, 3, 5, 5, 3]

counter = getSingle(arr1)

print (f"{counter[0]} occured {counter[1]} time(s)")

Output:

4 occured 1 time(s)
user_75053950
Related