Excelente video para mi frustración en tratar de aprender a programar 😢
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.
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
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
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
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)
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)
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 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
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).
Como tengo un arreglo de enteró con los números del cero a n. 1) ordenaria el arreglo de menor a mayor utilizando el método QuickSort. 2) utilizó el método de búsqueda binaria. creo una variable Num = 0 y voy buscando en el arreglo. si lo encuentra aumentó en 1 a la var Num y sigo buscando. sino, detengo la iteración y muestro la var Num que es el número que falta. elijo el peor caso para saber la complejidad: O(n^2) para el ordenamiento Quicksort O(log n) para la búsqueda binaria pero como el condicional If tiene el control de repetirlo o detenerlo no se como afecta a la fórmula. encontrar la complejidad y tiempo siempre me costó en la UNI
Lo que se me ocurre es x = sumatoria de arreglo completo - sumatoria de arreglo incompleto
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
Solución: n * (n + 1) / 2 - sum(array) Como sum() es una función que itera el arreglo en su totalidad la complejidad de este algoritmo es O(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 }
Ordenar_menor_a_mayor() Resultado =0 For i=0, i=n[i] i++ Resultado = i Return If Resultado ==0 Print( falta el número 0) Else Print (falta número {Resultado + 1}
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
no se, no estudió programación 🗿👍
Yo habría usado el factorial dividido por la multiplicación de todos los números del arreglo, excluyendo el cero y así sale directamente el número faltante.
@mistral_restfield