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