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

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)