Codility Problema 3.b — PermMissingElem
Solución de problemas de lógica computacional de la pagina https://app.codility.com/
Ingles
An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.
Your goal is to find that missing element.
Write a function:
def solution(A)that, given an array A, returns the value of the missing element.
For example, given array A such that:
A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5the function should return 4, as it is the missing element.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- the elements of A are all distinct;
- each element of array A is an integer within the range [1..(N + 1)].
Español
Se da una matriz A que consta de N números enteros diferentes. La matriz contiene números enteros en el rango [1 .. (N + 1)], lo que significa que falta exactamente un elemento. Tu objetivo es encontrar ese elemento que falta.
Escribe una función:
def solución (A)que, dada una matriz A, devuelve el valor del elemento que falta.
Por ejemplo, dada la matriz A tal que:
A [0] = 2 A [1] = 3 A [2] = 1 A [3] = 5la función debería devolver 4, ya que es el elemento que falta.
Escriba un algoritmo eficiente para las siguientes suposiciones:
- N es un número entero dentro del rango [ 0 .. 100.000 ];
- los elementos de A son todos distintos;
- cada elemento de la matriz A es un número entero dentro del rango [1 .. (N + 1)].
Entendiendo el problema
El problema plantea resolver efectivamente la búsqueda de un elemento perdido en una serie de números consecutivos. Si bien su resolución es fácil, como se explica en el siguiente item, su principal problema es que lo haga con un performance bueno para series de 1 a 100.000 valores
Entendiendo la Solución
Personalmente, plantee una resolución sencilla, como se visualiza en el diagrama de Venn, el valor faltante es aquel que no se encuentra en la intersección de las dos listas, es decir todo valor que se encuentre en A, pero no en B (se entiende que en ese caso, cada lista representa un espacio, ya sea A o B como en la gráfica). Esta solución es sencilla y práctica, sin embargo, es poco recomendable para un buen performance.
Existe otra solución, que optimiza el performance y que su funcionalidad es correcto. Esta solución usa los principios de series matemáticas, en este caso, es una Suma de Gauss, o una serie divergente. Este tipo de series tienen una formula comprobada que representa la sumatoria de sus valores, y que devolverá el valor de la serie completa sin tener que iterar toda la lista de valores.
Así la solución a este problema se resume en la diferencia de la suma de valores de la lista incompleta y la suma de la lista completa.
Código de Solución - Python
El código fuente de este problema y otros mas (HackerRank, Codility):
