Sacaría la suma total que debería tener (tomando en cuenta que están todos los números). Luego sumo el total real que tiene el arreglo (donde falta el número). Al final restaría la suma total con la real y el resultado es el número faltante. No sé si es la más eficiente, pero por lo menos creo que es más eficiente que recorrer todo el arreglo buscando el número.
Excelente video para mi frustración en tratar de aprender a programar 😢
Genra una lista: List = range(n) Y luego itera por cada numero de la misma y comprueba si esta en el original Si este no esta , ya tienes tu numero faltante
La mejor solución no puede ser una donde tengas que ordenar el array original porque eso tendría una complejidad de O(n log(n)). La solución mas sencilla es usar un Map o diccionario donde guardes como clave los números desde el 0 y todos sus valores iguales a 0, un vez hagas esto recorres el array y vas aumentando su valor en el map a 1. Una vez recorrido el array, ahora recorres el Map y cuando encuentres un valor igual a cero en el diccionario paras y retornas la clave asociada a ese valor, la complejidad del algoritmo es O(2n) que es lo mismo que O(n) y una complejidad espacial de O(n)
Tendria una variable que almacene el valor de la suma total del rango de numeros de 0 a n, recorrería el arreglo restando cada valor de los indices del arreglo donde un numero x falta dentro del rango, y el residuo o el numero resultante después de este proceso seria el numero que falta. El problema sugiere que siempre habra un numero faltante, pero en caso de ser valido y requerido identificar si es 0 el que falta o ninguno solo añadiría un contador, entonces el valor del contado igual a n indicaria que 0 falta, y si el valor del contador es igual a n+1 entonces ninguno falta. La complejidad en tiempo seria O(n) y en espacio O(1).
python ans = (n * (n + 1) // 2) - sum(array)
A mi se me ocurre sacar el numero mayor y menor de la lista original, crear una nueva que contenga todos y hacer una resta de las dos listas como conjuntos, el elemento que quede es el faltante
Ordenar y restar los numeros en pares a medida que se ordenan, if a - b = -2 then print (a + 1) y ahi tienes el numero que falta :3
Lo que se me ocurre es x = sumatoria de arreglo completo - sumatoria de arreglo incompleto
Yo lo que haría es ordenar el arreglo. Luego cuando lo recorra comparo si Array[n] + 1 = Array[n + 1] Si es igual sigo recorriendo, si no, devuelvo Array[n]+ 1 cono el valor que falta
Sort no es la forma más eficiente porque es O(n*log(n)). Se puede hacer en O(n) con la función suma: def faltante(arr): n = len(arr) return n*(n+1)/2 - sum(arr)
Es facil, primero un sort para ordenar el array y luego un busqueda binaria para encontrar el número que falta, claro que con unas cuantas modificaciones aqui compararias el mid con el numero que deberia ir en el mid, me explico en el array de ejemplo el primer mid es el 5, al ordenar la lista y comparar que hay en la posicion 5 nos encontrariamos el 6, entonces quiere decir que el numero que falta esta del lado izquierdo, volveria a hacer el ciclo ahora con mid 3, al comparar y ver que mid 3 es 3 quiere decir que esta al lado derecho del array, ahora con low=3 high=5 el mid seria 4 al ver que en el array 4 esta el 5 y no quedan mas interacciones devolveria que falta el numero 4, y asi con cualquier ejemplo
Se saca una lista del min de la lista base al número n y luego se aplicca un loop con una condicional para que compara con una lista creada con los valores del min a n con conteos de 1 en 1 para ver que numero falta y que luego se adicione ese numero en la lista de todos los numeros
n define el intervalo de la longitud del array en [0, n]. Si n+1 es mayor que la longitud del array, significa que la faltan (n+1) - length elementos. Si el array está vacío y/o no es null (o lo que sea), entonces los elementos faltantes son n+1 y simplemente habría que generar los números del intervalo [0, n]. Si el array no está vacío y (n+1) - length es positivo o (n+1) - length = 0 pero hay repeticiones, habría que identificar cada uno de esos elementos faltantes en otro array. Si el elemento está en el intervalo, pero no en el array, se agrega. Esto aún funcionaría con repeticiones. Tiene mayor complejidad de espacio, ya que ocupa más memoria ((n+1) - length) * elem_size y es más lento debido a los accesos de memoria extra (por el nuevo array), pero es la solución más consistente ante cualquier caso. La complejidad temporal es la misma, O(n). Si el array no está vacío, y (n+1) - length = 0 y no hay repeticiones, de todas formas habría que verificar cada elemento del array, ya que podrían estar generados con un intervalo diferente. Es decir, que en lugar de [1,2,3,4,5] tuviera [2,3,4,5,6]. Y si finalmente no hubiera elementos faltantes del intervalo previamente definido por n, entonces se devuelve un null pointer, o un array vacío o lo que sea conveniente para indicar que no hay elementos faltantes. La otra solución O(n) es más eficiente en complejidad de espacio, pero no es tan consistente en diferentes escenarios. Si el array no está vacío, y (n+1) - length = 1, y no existen repeticiones, se saca la sumatoria del intervalo ( n(n+1)/2 ), y se resta con la sumatoria de los elementos del array, siendo el resultado el número faltante. Por ejemplo, si n = 5, entonces la sumatoria del intervalo es 15. Y si el array es: [0, 4, 1, 2, 5], entonces 15 - (4+1+2+5) = 3. Ahora, si el array es [1,2,3,4,5] el elemento faltante es 15 - 15 = 0. Entonces esto siempre va a funcionar siempre y cuando la cantidad de elementos faltantes sea 1 y no existan elementos repetidos. Pero la única forma de que esto funcione consistentemente es que la función tenga una flag donde se asegure que no existan repeticiones. La existencia de repeticiones eliminaría el número faltante en sí y otro número ya existente, por ejemplo: en [0,0,3,4,5] falta 1 y 2, y en [1,1,3,4,5] falta 0 y 2. Ahora, esto es cuando (n+1) - length es no-negativo, pero la cosa cambia si (n+1) - length es negativo, esto significa que o sobran elementos o existen elementos repetidos pero sin faltantes, o existen muchos elementos repetidos y también faltantes. No existe una regla para los sobrantes, así que será lo mismo que en el caso donde no haya elementos faltantes. Y en ambos casos se aplica la solución normal no optimizada. Y ya, creo que esa es la respuesta
creo q tengo una solucion,si el arreglo es de numeros continuas hasta N pero falta un numero,se podria hacer otro arreglo aparte sabiendo cual es N (y rellenendo este arreglo hast el N) y compara los numeros de ambos arreglos con un boleano claro esta si solo es que falte un numero en el array,si falta mas de un numero seria mejor creo q usar una variable contador,llendo a los anterior solo seria compara los numero y ver si un numero del nuevo array esta entre ellos en caso de que no simplemente se le cambia el valor al boleano y se guarda el numero en otra variable para mostrarlo
En mi caso haria lo siguiente, un bucle que sume N+1 inicie desde 0 y que vaya buscando una coincidencia en el array, al no conseguir coincidencia muestre el último dígito que sumo.
Ordenar el arreglo y tener el otro arreglo de número completo comparar uno a uno y con un if de si si el número es diferente indicarlo e interrumpir el ciclo para finalizar el programa
no se, no estudió programación 🗿👍
creo que la solución más sencilla es la siguiente: una función en la que se defina un booleano en true y un retorno en -1. en un for (con inicio en i=0, que vaya hasta que i<= n y mediane el booleano este en true) recorres todo el array y en un if revisas si ese número de iteración esta incluido en el array (!array.includes(i)), si esta incluido en el array volves al ciclo del for, si no esta incluido pones el booleano en false (para cortar el for) y el retorno que estaba en -1 lo pones en el número del for (i). function encontrarFaltante(n,array) { let ok = true let retorno = -1 for (let i = 0; i <= n && ok; i++) { if (!array.includes(i)){ ok = false retorno = i } } return retorno }
@mistral_restfield