Codility OddOccurrencesInArray Problem - Recursion and Python

Question

I am trying to use recursion to solve the OddOccurrencesInArray Problem in Codility, in which

• we are given an array with N elements, N is always odd
• all of the elements of the array except for one has a total even number of occurrences
• we need to write code that returns the one unpaired value

For example, if the array given is [9, 3, 9, 3, 7, 9, 9], the code must return 7, because that is the only element in the array which is unpaired.

My solution pseudocode/thought process was:

• sort the array
• if the first two elements are equal to each other, remove them and run the solution algorithm again recursively on the array minus the first two elements (after sorting) i.e. if the unpaired element is not found, we keep reducing the size of the array
• if the first two elements are NOT equal to each other, the first element of the array must be the unpaired item

My implementation was:

def solution(A):
    # write your code in Python 3.6
    if len(A) > 1: 
        A = sorted(A)
        if A[0] != A[1]:
            return A[0]
        else:
            solution(A[2:])
    else:
        return A[0]

I keep getting the error message

Invalid result type, int expected, <class 'NoneType'> found. RUNTIME ERROR (tested program terminated with exit code 1)

Can anyone help me figure out what this means and how I can correct it? Algorithmically, I think my solution is sound, and I don't understand why it isn't returning the integer values as I specified.

Answer 1

Another Python solution 100%

There is another solution where we can use XOR logic.

First Let's remember together what does XOR mean:

We can recognize that if we have for Input A and Input B the same bit then, XOR Output will be zero.

Also, if we take the bit XOR of any number with zero that definitely give the same number because the bits of the number will result in the same bits which means the same number.

Now, to solve the problem with the XOR logic, we start by defining a number that will hold the result of the XOR output each time, so first, we start with zero and I said earlier that zero with any number gives the same number.

But if we get a different number next time, the XOR result will be some unknown number.

In the end, for sure the number that did not pair will be returned.

Since a solution like this will be possible with only one loop, then we need to loop through all the elements and if we do break at some point, the result of the XOR would be some number we do not need!

So we need to make sure that we loop through the whole array once and then because of the fact that bit XOR of the same number would return zero. So that, we remain at the end with the number that is unpaired with anything.

Detected time complexity: O(N) or O(N*log(N))

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

Answer 2

I would suggest a different approach altogether. A recursive approach is not incorrect, however repeated calls to sorted is highly inefficient, especially if the input is significantly large.

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  return list(s)

input = [9, 3, 9, 3, 7, 9, 9]
solve(input)

We can visualize s over the course of the evaluation -

{}     # <- initial s
{9}    # <- 9 is added
{9,3}  # <- 3 is added
{3}    # <- 9 is removed
{}     # <- 3 is removed
{7}    # <- 7 is added
{7,9}  # <- 9 is added
{7}    # <- 9 is removed

The finally list(s) is returned converting {7} to [7]. To output the answer we can write a simple if/elif/else -

unpaired = solve(input)

if (len(unpaired) < 1):
  print("there are no unpaired elements")
elif (len(unpaired) > 1):
  print("there is more than one unpaired element")
else:
  print("answer:", unpaired[0])

Another option is to have solve return the first unpaired element or None -

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  for v in s:
    return v          # <- immediately return first element

answer = solve(input)

if answer is None:
  print("no solution")
else:
  print("the solution is", answer)