pythonarraysrecursionnonetype

Codility OddOccurrencesInArray Problem - Recursion and Python


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

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:

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.


Solution

  • 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)