.

Thursday, August 4, 2016

Odd Occurrences In Array Algo and Implementation in Python

A non-empty zero-indexed array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.
For example, in array A such that:
A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9
  • the elements at indexes 0 and 2 have value 9,
  • the elements at indexes 1 and 3 have value 3,
  • the elements at indexes 4 and 6 have value 9,
  • the element at index 5 has value 7 and is unpaired.

XOR Operation :  It is a bit wise logical operation that only returns true if both the inputs are the same

Properties of XOR Here are several useful properties of XOR. This applies to plain XOR and bitwise XOR.
  • x (+) 0 = x  XORing with 0 gives you back the same number. Thus, 0 is the identity for XOR. x (+) 1 = \x  XORing with 1 gives you back the negation of the bit. Again, this comes from the truth table. For bitwise XOR, the property is slightly different: 
  • x ^ ~0 = ~x . That is, if you XOR with all 1's, the result will be the bitwise negation of x. 
  • x (+) x = 0  XORing x with itself gives you 0. That's because x is either 0 or 1, and 0 (+) 0 = 0 and 1 (+) 1 = 0. 
  • XOR is associative.That is: (x (+) y) (+) z = x (+) (y (+) z). You can verify this by using truth tables. 
  • XOR is commutative.That is: x (+) y = y (+) x.
 Implementation1: Using Bit wise XOR(^)

1
2
3
4
5
def solution(A):
    result = 0
    for number in A:
        result = result ^ number
    return result

Counter Collection : A Counter is a dict subclass for counting hashables objects. More details can be found in python documentation https://docs.python.org/3/library/collections.html#collections.Counter
 
Implementation2: Using Counter Collection
 
1
2
3
4
5
from collection import Counter
def solution(A):
    for i in Counter(A):
        if Counter(A)[i]%2 == 1:
            return i

No comments :

Post a Comment

There was an error in this gadget