Finding the odd integer that does not form the pair in the list

Question

I am given a problem to solve ! which is

A non-empty 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.

Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given 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 function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

    N is an odd integer within the range [1..1,000,000];
    each element of array A is an integer within the range [1..1,000,000,000];
    all but one of the values in A occur an even number of times.

I think I am only half way to solve the problem:

def findOddItem(A):
    for i, item in enumerate(A): # look to left not immidiate one
        if A[i] != A[i - 2]:
            print A[i]

but this looks like printing the wrong result..

Possible duplicate of [find the only unpaired element in the array](https://stackoverflow.com/questions/2644179/find-the-only-unpaired-element-in-the-array) — pault, Oct 19 '18 at 04:03
For the first two elements of `A`, `i - 2` goes back past the beginning of the array so you get wrong results. You can do `if A[i] != A[i - 2] and (i - 2) > 0:`, which will make your code "work" for the example data. But I don't see anything in the problem specification that says the paired values will always be two elements apart, I suspect you might need to rethink your approach. — Marius, Oct 19 '18 at 04:06
_Write an efficient algorithm_ can mean a lot of things. Processing efficient? Memory efficient? Besides, SO is not a homework writing service but here's a hint: nowhere in the assignment does it say that the elements have to be paired with their penultimate element - the pair can be anywhere in the array. — zwer, Oct 19 '18 at 04:08

score 3 · Answer 1 · answered Oct 19 '18 at 04:30

I would go with reduce() (moved to functools.reduce() in Python 3.x) in combination with operator.xor():

# Uncomment for Python 3.x:
# from functools import reduce
import operator

def solution(A):
    return reduce(operator.xor, A)

arr = [9, 3, 9, 3, 9, 7, 9]

print(solution(arr))  # 7

It's an, as clean as it gets, O(n) solution.

Akshaya Kumar T · Accepted Answer · 2018-10-19T04:18:23.827

1

You could use "or" bitwise operator. Since all elements occur twice except one element they would cancel each other leaving the element that has occurred only once.

def findSingleOccurance( arr, n): 

    res = arr[0] 

    # Do XOR of all elements and return 
    for i in range(1,n): 
        res = res ^ arr[i] 

    return res

Time complexity O(n) Space Complexity O(1). Hope this helps.

edited Oct 19 '18 at 04:18

answered Oct 19 '18 at 04:10

Akshaya Kumar T

134
2
13

score 1 · Answer 3 · answered Oct 19 '18 at 04:14

1

Since there is no condition that all but one elements occur twice, I guess it could also mean 4, 6, ... , times.

In this case, I would rather use numpy.bincount to see which integer has an odd count.

a = [1,1,2,2,3,3,5,3,3,4,5,5,5,10,10]
a_cnt = list(numpy.bincount(a))
for i in a_cnt:
    if i != 0 and i%2 == 1:
        print(a_cnt.index(i))
# 4

answered Oct 19 '18 at 04:14

Chris

29,127
3
28
51

The question asks for an "efficient" solution, presumably referring to its big-O runtime. Do you know what the efficiency of `bincount` is? – Marius Oct 19 '18 at 04:18

score 0 · Answer 4 · answered Oct 19 '18 at 04:50

You could use "xor" bitwise operator. Since all elements occur twice except one element they would cancel each other leaving the element that has occurred only once.

def SingleOccurance( arr, n): 

result = arr[0] 

# Do XOR of all elements and return as 'a' xor 'a' is 0 and except single 
# occured number rest will turn to 0 and 'a' xor 0 is 'a'
for i in range(1,n): 
    result = res ^ arr[i] 

return result

Or

We can sum the bits in the same positions for all the numbers and take modulo with 3. The bits for which sum is not multiple of 3, are the bits of number with a single occurrence.

Let us consider the example array {5, 5, 5, 8}. The 101, 101, 101, 1000

Sum of first bits%3 = (1 + 1 + 1 + 0)%3 = 0

Sum of second bits%3 = (0 + 0 + 0 + 0)%0 = 0

Sum of third bits%3 = (1 + 1 + 1 + 0)%3 = 0

Sum of fourth bits%3 = (1)%3 = 1 Hence number which appears once is 1000

Code:

INT_SIZE = 32

def getSingle(arr, n) : 

    # Initialize result 
    result = 0

    # Iterate through every bit 
    for i in range(0, INT_SIZE) : 

        # Find sum of set bits  at ith position in all array elements 
        sm = 0
        x = (1 << i) 
        for j in range(0, n) : 
            if (arr[j] & x) : 
                sm = sm + 1

        # The bits with sum not multiple of 3, are the 
        # bits of element with single occurrence. 
        if (sm % 3) : 
            result = result | x 

    return result

Finding the odd integer that does not form the pair in the list

4 Answers4