CODEWITHSUNDEEP
pythonarrayslist
Chang Zhao
Chang Zhao

Reputation: 631

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

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..

Upvotes: 2

Views: 1556

Answers (4)

sahushivam
sahushivam

Reputation: 109

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

Upvotes: 0

zwer
zwer

Reputation: 25809

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.

Upvotes: 3

Akshaya Kumar T
Akshaya Kumar T

Reputation: 144

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.

Upvotes: 1

Chris
Chris

Reputation: 29742

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

Upvotes: 1

Related Questions