Problema Codility OddOccurrencesInArray – Recursión y Python.
Estoy intentando usar la recursión para resolver el problema OddOccurrencesInArray en Codility, en el cual:
- se nos da un array con N elementos, siendo N siempre impar
- todos los elementos del array, excepto uno, tienen un número total de ocurrencias par
- necesitamos escribir código que devuelva el valor no emparejado
Por ejemplo, si el array dado es [9, 3, 9, 3, 7, 9, 9], el código debe devolver 7, porque es el único elemento en el array que no está emparejado.
Mi pseudocódigo/proceso de pensamiento para la solución fue:
- ordenar el array
- si los primeros dos elementos son iguales entre sí, eliminarlos y ejecutar el algoritmo de solución de nuevo de manera recursiva en el array menos los primeros dos elementos (después de ordenarlos), es decir, si no encontramos el elemento no emparejado, seguimos reduciendo el tamaño del array
- si los primeros dos elementos NO son iguales entre sí, el primer elemento del array debe ser el elemento no emparejado
Mi implementación fue:
def solution(A):
# escriba su código en 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]
Sigo obteniendo el mensaje de error:
Tipo de resultado inválido, se esperaba int, se encontró
ERROR DE TIEMPO DE EJECUCIÓN (el programa probado finalizó con el código de salida 1)
¿Alguien puede ayudarme a entender qué significa esto y cómo puedo corregirlo? A nivel algorítmico, creo que mi solución es correcta, y no entiendo por qué no está devolviendo los valores enteros como lo he especificado.
davy.ai
El mensaje de error te está indicando que tu función está devolviendo None (que se representa como), cuando se espera que devuelva un número entero. Esto sucede porque en la llamada recursiva (es decir, cuando llamas a solution(A[2:]) de nuevo), en realidad no estás devolviendo el valor que es retornado por esa llamada.
Para solucionar esto, puedes agregar una instrucción de retorno antes de la llamada recursiva para asegurarte de que el valor que retorna sea pasado por la pila de llamadas:
Con esta modificación, la función ahora debería devolver el valor entero correcto para el elemento sin pareja.