Dado un conjunto entero tal que cada elemento ocurre 3 veces, excepto un elemento, que ocurre solo una vez, ¿cómo encuentro ese único elemento en el espacio O (1) y en la complejidad del tiempo O (n)?

Aunque la respuesta de Leo Polovets tiene una intuición útil, no se puede implementar de manera eficiente porque las computadoras no tienen operaciones para trabajar en forma ternaria. Se necesitan operaciones [math] O (b) [/ math] para convertir un número binario de bit [math] b [/ math] a ternario y viceversa, durante un tiempo total [math] O (nb) [/ math].

Sin embargo, el algoritmo se puede simplificar enormemente encontrando las sumas de cada dígito binario mod 3 en lugar de las sumas de cada dígito ternario mod 3. Eso se puede implementar utilizando operaciones bit a bit, almacenando las ubicaciones de los 1 y 2 en variables de máscara de bits separadas:

def single(array): ones, twos = 0, 0 for x in array: ones, twos = (ones ^ x) & ~twos, (ones & x) | (twos & ~x) assert twos == 0 return ones 

Esto se ejecuta en tiempo [matemático] O (n) [/ matemático].

---

Podemos generalizar de “3 veces” a “[matemáticas] k [/ matemáticas] veces” en [matemáticas] O (n \ log k) [/ matemáticas] tiempo.

Hay dos enfoques para esta solución, uno sugerido por Leo Polovets:

Aquí hay una implementación para ello:

1. Una forma:
Complejidad de tiempo: O (n * log k) => donde “log k” es el dígito máximo de la base r-radix se utiliza para representar una repetición de un número establecido r-veces.

 public class Solution { private static String computeXorBase(String firstNum, String scndNum, int radix) { int lengthFrst = firstNum.length(); int lengthscndNum = scndNum.length(); if (lengthFrst > lengthscndNum) { String swap = firstNum; firstNum = scndNum; scndNum = swap; } lengthFrst = firstNum.length(); lengthscndNum = scndNum.length(); int diffLength = lengthscndNum - lengthFrst; StringBuilder result = new StringBuilder(); for (int i = lengthFrst - 1; i >= 0; i--) { result.insert(0, (Integer.valueOf(firstNum.charAt(i) + "") + Integer.valueOf(scndNum.charAt(diffLength + i) + "")) % radix); } result.insert(0, scndNum.subSequence(0, diffLength)); return result.toString(); } private static String convertToBaseN(int num, int radix) { if (radix < 0) { radix = 10; } if (num < 0) { long l = Math.abs((long) Integer.MIN_VALUE) - Math.abs(num); l = l + 2147483648l; return Long.toString(l, radix); } else { return Integer.toString(num, radix); } } public int singleNumber(int[] A) { if (A == null || A.length <= 2) { return A[0]; } int size = A.length; int radix = 3; String result = convertToBaseN(A[0], radix); for (int i = 1; i < size; i++) { result = computeXorBase(result, convertToBaseN(A[i], radix), radix); } return (int) (long) Long.valueOf(result, radix); } } 

2. Otra forma:

implementación en Java,

 public class Array3Rpt1Unq{ public static void main(String[] args) { int B[] = {2,4,4,4};//{4,4,2};//{4,4,4,2}; //bit-sets for those which are visited odd(one time only) number of times int ones = 0 ; //bit-sets for those which are visited two times. int twos = 0 ; //just to reset twos and ones if the number are visited three times int not_threes; for( int x:B ) { twos |= ones & x ; ones ^= x ; not_threes = ~(ones & twos) ; ones &= not_threes ; twos &= not_threes ; } //finally ones contains the non-repeated number printf("\n unique element = %d \n", ones ); } } 

Explicacion:

El código funciona en una línea similar con la cuestión de "encontrar el elemento que aparece una vez en una matriz, que contiene otros elementos que aparecen dos veces". La solución es XOR todos los elementos y obtienes la respuesta.

Básicamente, hace uso del hecho de que x ^ x = 0. Por lo tanto, todos los elementos emparejados obtienen XOR y desaparecen dejando el elemento solitario.
Dado que la operación XOR es asociativa, conmutativa ... no importa de qué manera los elementos aparezcan en la matriz, todavía obtenemos la respuesta.

Ahora, en la pregunta actual, si aplicamos la idea anterior, no funcionará porque, tenemos que tener cada elemento único apareciendo varias veces. Entonces, en lugar de obtener la respuesta, terminaremos obteniendo XOR de todos los elementos únicos que no es lo que queremos.

Para rectificar este error, el código utiliza 2 variables.
ones: en cualquier momento, esta variable contiene XOR de todos los elementos que tienen
apareció "solo" una vez.
dos: en cualquier momento, esta variable contiene XOR de todos los elementos que tienen
apareció "solo" dos veces.

Entonces, si en algún momento,
1. Aparece un nuevo número: obtiene XOR de la variable "unos".
2. Se repite un número (aparece dos veces): se elimina de "unos" y se envía XOR a la
variable "dos veces".
3. Aparece un número por tercera vez: se elimina de "unos" y "dos veces".

La respuesta final que queremos es el valor presente en "unos", porque contiene el elemento único.

Entonces, si explicamos cómo ocurren los pasos 1 a 3 en el código, ya hemos terminado.
Antes de explicar los 3 pasos anteriores, veamos las últimas tres líneas del código,

not_threes = ~ (unos y dos)
unos & = no_tres
dos & = no_tres

Todo lo que hace es que los 1 comunes entre "unos" y "dos" se convierten a cero.

Para simplificar, en todas las explicaciones a continuación, considere que solo tenemos 4 elementos en la matriz (un elemento único y 3 elementos repetidos, en cualquier orden).

Explicación para el paso 1
————————
Digamos que aparece un nuevo elemento (x).
SITUACIÓN ACTUAL - Ambas variables - "unos" y "dos" no han registrado "x".

Observe la declaración "dos | | unos y x".
Dado que la representación en bits de "x" no está presente en "unos", la condición AND no produce nada. Entonces "dos" no obtiene una representación de "x" en bits.
Pero, en el siguiente paso "ones ^ = x" - "ones" termina agregando bits de "x". Así, el nuevo elemento se graba en "unos" pero no en "dos".

Las últimas 3 líneas de código, como ya se explicó, convierte los "unos" y "dos" b / w comunes de 1 en ceros.
Desde ahora, solo "unos" tiene "x" y no "dos" - las últimas 3 líneas no hacen nada.

Explicación para el paso 2.
————————
Digamos que un elemento (x) aparece dos veces.
SITUACIÓN ACTUAL - "unos" ha grabado "x" pero no "dos".

Ahora, debido a la afirmación, "dos | | unos & x" - "dos" termina obteniendo bits de x.
Pero debido a la declaración, "ones ^ = x" - "ones" elimina "x" de su representación binaria.

Nuevamente, las últimas 3 líneas de código no hacen nada.
Así que, en última instancia, "dos" termina obteniendo bits de "x" y "unos" termina perdiendo bits de "x".

Explicación para el paso 3.
————————-
Digamos que un elemento (x) aparece por tercera vez.
SITUACIÓN ACTUAL - "unos" no tiene una representación en bits de "x" pero sí "dos".

Aunque "unos & x" no produce nada ... "dos" en sí mismo tiene una representación de "x". Entonces, después de esta declaración, "dos" tiene una representación en bits de "x".
Debido a "ones ^ = x", después de este paso, "one" también termina obteniendo una representación en bits de "x".

Ahora las últimas 3 líneas de código eliminan los 1 comunes de "unos" y "dos", que es la representación en bits de "x".
Por lo tanto, tanto "unos" como "dos" terminan perdiendo bits de representación de "x".

Aquí hay un video sobre este problema:

Algoritmo 1:
1: Cree la matriz countSetBits [] de tamaño 32 (para representar un entero de 32 bits) donde,
countSetBits [i] representa el recuento de un bit establecido de todos los elementos en la matriz de entrada.
Inicialmente, todos los elementos de la matriz countSetBits [] son ​​0.
2: recorra todos los elementos de la matriz de entrada para completar countSetBits, siguiendo el paso 3 para cada uno de ellos.
3: Tome el elemento y verifique sus bits establecidos. Si se encuentra que el bit i-ésimo está establecido, entonces en la matriz countSetBits [] incremente el recuento del elemento en el índice ‘i’.
4: Después de finalizar la operación anterior para todos los elementos de la matriz de entrada, los elementos de countSetBits [] representarían la cuenta de todos los bits establecidos en los elementos de la matriz de entrada.
Realice la operación de módulo N en cada elemento de la matriz countSetBits [].
La operación de los módulos N eliminará el recuento de bits de elementos establecidos que ocurren N veces.
Después de la operación del módulo N, si obtenemos el resto 1 en un índice ‘j’, eso significa que en el número que ocurre solo una vez, tenemos un bit establecido en el índice ‘j’.
Después de la operación del módulo N en cada elemento, la matriz countSetBits [] representa la representación en bits del elemento requerido. Establecer bits individuales en la variable ‘solución’.

Por ejemplo: considere la matriz:

Consulte la implementación y la visualización del algoritmo que se proporciona en este enlace:

Encuentre el elemento que aparece una vez en una matriz

Algoritmo 2:
1: Inicializar solución = 0.
2: Establezca bits individuales de ‘solución’ siguiendo el paso 3.
3: Para establecer la posición de bit de ‘solución’, calcule la suma de todos los bits de bit de todos los elementos en la matriz de entrada y modifíquelo por N.

Espero que esto ayude.

Una forma de hacer esto en el espacio O (1) y el tiempo de ejecución esperado de O (n) será usar el método de partición como se hace en forma rápida. El algoritmo funciona como

1. Elija un elemento aleatorio como pivote y particione la matriz por él (con el lado izquierdo que contiene valores menores que iguales al pivote)
2. Ahora verifique el índice de pivote después de la partición, digamos k, si k es divisible por 3 (es decir, k% 3 == 0), entonces el elemento único se encuentra a la derecha de lo contrario en la partición izquierda.
3. Aplique los pasos 1 nuevamente en la partición que obtiene del paso 2

El tiempo de ejecución amortizado será O (n) pero en el peor de los casos O (n ^ 2), estoy diciendo que O (1) espacio en el supuesto de que la reordenación de la matriz no es un problema.

Un número aparece tres veces, cada bit (0 o 1) también aparece tres veces. Si se agrega cada bit de números que aparecen tres veces, la suma de cada bit debe ser múltiplo de 3.

Supongamos que se agrega cada bit de números (incluido el número único) en la matriz de entrada. Si la suma de un bit es múltiplo de 3, el bit correspondiente en el número único es 0. De lo contrario, es 1.

La solución se puede implementar en Java como el código que se detalla a continuación:

  public static int FindNumberAppearingOnce (int [] números) {
     int [] bitSum = new int [32];
     para (int i = 0; i <32; ++ i) {
         bitSum [i] = 0;
     }
       
     para (int i = 0; i  = 0; --j) {
             int bit = números [i] & bitMask;
             if (bit! = 0) {
                 bitSum [j] + = 1;
             }
                
             bitMask = bitMask << 1;
         }
     }
       
     int resultado = 0;
     para (int i = 0; i <32; ++ i) {
         resultado = resultado << 1;
         resultado + = bitSum [i]% 3;
     }
      
     resultado de retorno;
 } 

Solía ​​escribir un blog sobre este problema y, si tiene intereses, visite el número 50: números que aparecen una vez.

Entrada: arr [] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
Salida: 2

Podemos usar la ordenación para hacerlo en tiempo O (nLogn). También podemos usar el hashing, pero la complejidad del hash en el peor de los casos puede ser mayor que O (n) y el hashing requiere espacio adicional.

La idea es usar operadores bit a bit para una solución que es O (n) tiempo y usa O (1) espacio extra. La solución no es fácil como otras soluciones basadas en XOR, porque todos los elementos aparecen un número impar de veces aquí. La idea está tomada de aquí.

Ejecute un bucle para todos los elementos en la matriz. Al final de cada iteración, mantenga los siguientes dos valores.

unos: los bits que han aparecido por primera vez o por cuarta vez o por séptima vez … etc.
dos: los bits que han aparecido 2ª vez o 5ª vez u 8ª vez … etc.

Finalmente, devolvemos el valor de ‘unos’

¿Cómo mantener los valores de ‘unos’ y ‘dos’?
‘unos’ y ‘dos’ se inicializan como 0. Para cada elemento nuevo en la matriz, encuentre los bits de conjunto comunes en el nuevo elemento y el valor anterior de ‘unos’. Estos bits de conjunto comunes son en realidad los bits que deben agregarse a ‘dos’. Así que haga OR bit a bit de los bits de conjunto comunes con ‘dos’. ‘dos’ también obtiene algunos bits adicionales que aparecen por tercera vez. Estos bits adicionales se eliminan más tarde.
Actualice ‘unos’ haciendo XOR del nuevo elemento con el valor anterior de ‘unos’. Puede haber algunos bits que aparecen por tercera vez. Estos bits adicionales también se eliminan más tarde.

Ambos ‘unos’ y ‘dos’ contienen esos bits adicionales que aparecen por tercera vez. Elimine estos bits adicionales descubriendo los bits de conjunto comunes en ‘unos’ y ‘dos’.

---

  #include 
 
 int getSingle (int arr [], int n)
 {
     int unos = 0, dos = 0;
 
     int common_bit_mask;
 
     // Tomemos el ejemplo de {3, 3, 2, 3} para entender esto
     para (int i = 0; i 
  Salida: 
  2 


  Complejidad de tiempo: O (n) 
  Espacio auxiliar: O (1) 
  Implementación: Ideone.com 
    

Defina una nueva adición con el sistema base 3 sin exceso de flujo 0 + 1 = 1, 0 + 2 = 2, 1 + 1 = 2,1 + 2 = 0, 2 + 1 = 0; 2 + 2 = 1.
Cambie todos los números al número base 3 y súmelos, obtendrá el número con base 3. Convierta el número base 3 en número decimal
ejemplo 12,4,7,4,12,12,4. Paso 1:
Número con 12 +4 = 110 + 011 = 121,
(12 + 4) +7 = 121 + 021 = 112,
(12 + 4 + 7) + 4 = 112 + 011 = 120,
(12 + 4 + 7 + 4) + 12 = 120 + 110 = 200,
(12 + 4 + 7 + 4 + 12) + 12 = -200 + 110 = 010,
(12 + 4 + 7 + 4 + 12 + 12) + 4010 + 011 = 021
Paso 3: transferencia inversa: 021 = 7

Por lo tanto, necesita espacio constante, suma antigua, número actual y suma nueva. Y atravesar la matriz solo una vez

*** ACTUALIZACIÓN ***
Como señaló John Kurlak, el algoritmo propuesto a continuación tiene un defecto fatal. No funcionará en ciertas circunstancias donde los valores triples son divisibles por 3, o el singleton es divisible por 3. No se me ocurre ninguna forma de solucionarlo sin asignar dinámicamente algo de memoria para realizar un seguimiento de dichos valores, pero eso violaría la restricción de espacio O (1).

==================================

1. Haga un pase sobre la matriz, sumando los enteros positivos en una variable, los negativos en otra, y en una tercera variable cuente los valores cero.

2. Si el recuento de ceros es 1, entonces ya está.

3. Si no, haga un segundo pase. Durante ese pase, reste cada valor positivo de la suma positiva y vea si el resultado es divisible por 3 (usando el módulo 3). Si es así, has encontrado el valor. Haga lo mismo para los valores negativos.

Este algoritmo requiere como máximo 2 pasadas y, en el mejor de los casos, 1 pasada, y también lo es O (n).

Requiere solo 3 variables enteras y cumple con el requisito de “memoria constante”.

Funciona porque, si todos los valores menos uno en la matriz existen 3 veces, restando el singleton de la suma dará como resultado una suma que debe ser divisible por 3 (si todos los valores sumados son del mismo signo).

Aquí está el algoritmo en python:

algunos_valores = [1,4,7,13,17]

# crear una matriz que contenga tres de cada valor y un valor diferente (9)
the_array = some_values ​​+ [9] + some_values ​​+ some_values

imprimir the_array

# inicializar el contador y los acumuladores
sum_pos = 0
sum_neg = 0
count_zero = 0

# primer pase
# – suma los valores positivos y negativos
# – cuenta los valores cero
para v en the_array:
si v == 0:
count_zero + = 1
elif v> 0:
sum_pos + = v
más:
sum_neg + = v

# prueba cero
# – ver si había un valor único que era cero
si count_zero == 1:
print “La respuesta es cero”
sys.exit (0)

# inicializa la respuesta
respuesta = “ninguno encontrado”

# segundo pase
# – ver si la suma menos un solo valor es divisible por 3
para v en the_array:
test_pos = sum_pos – v
print “v = {0: 3}, sum_pos = {1}, test_pos = {2}, mod3 = {3}”. format (v, sum_pos, test_pos, test_pos% 3)

if (test_pos% 3) == 0:
respuesta = v
descanso

test_neg = sum_neg – v
if (test_neg% 3) == 0:
respuesta = v
descanso

print “La respuesta es:”, respuesta

Aquí está la salida:

[1, 4, 7, 13, 17, 9, 1, 4, 7, 13, 17, 1, 4, 7, 13, 17]
v = 1, sum_pos = 135, test_pos = 134, mod3 = 2
v = 4, sum_pos = 135, test_pos = 131, mod3 = 2
v = 7, sum_pos = 135, test_pos = 128, mod3 = 2
v = 13, sum_pos = 135, test_pos = 122, mod3 = 2
v = 17, sum_pos = 135, test_pos = 118, mod3 = 1
v = 9, sum_pos = 135, test_pos = 126, mod3 = 0
La respuesta es: 9

Lo siguiente es O (n) complejidad de tiempo y O (1) método de espacio extra sugerido por geeks. Podemos sumar los bits en las mismas posiciones para todos los números y tomar un módulo con 3. Los bits para los que la suma no es múltiplo de 3, son los bits de número con una sola ocurrencia.
Consideremos la matriz de ejemplo {5, 5, 5, 8}. Los 101, 101, 101, 1000
Suma de los primeros bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Suma de segundos bits% 3 = (0 + 0 + 0 + 0)% 0 = 0;
Suma de terceros bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Suma de cuartos bits% 3 = (1)% 3 = 1;
Por lo tanto, el número que aparece una vez es 1000

A continuación se presenta otro método de complejidad de tiempo O (n) y O (1) espacio extra. Podemos sumar los bits en las mismas posiciones para todos los números y tomar el módulo con 3. Los bits para los que la suma no es múltiplo de 3, son los bits de número con una sola ocurrencia.
Consideremos la matriz de ejemplo {5, 5, 5, 8}. Los 101, 101, 101, 1000
Suma de los primeros bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Suma de segundos bits% 3 = (0 + 0 + 0 + 0)% 0 = 0;
Suma de terceros bits% 3 = (1 + 1 + 1 + 0)% 3 = 0;
Suma de cuartos bits% 3 = (1)% 3 = 1;
Por lo tanto, el número que aparece una vez es 1000

Suponga que el número es un número de un solo bit. Ahora cree una máquina de estados finitos con 3 estados 0, 1 y 2. El estado representa el número de 1s módulo 3. Una entrada de 0 no cambiará el estado. Una entrada de 1 cambiará el estado de 0 a 1, 1 a 2 y 2 a 0.
Los estados 0, 1 y 2 se pueden representar de la siguiente manera: 00, 01 y 10. Ahora use 2 variables ayb para almacenar los bits del estado.
Entonces, esencialmente tiene una entrada (ya sea 0 o 1) que cambia el valor de las variables ayb a sus nuevos valores (según la máquina de estados). Podemos llegar a una expresión usando OR, AND, XOR, NEGATION que transforma los viejos valores de ayb en sus nuevos valores. Los nuevos valores serán una función de los antiguos valores de a y by la entrada.
Si los estados son: 0 (a = 0 b = 0), 1 (a = 0, b = 1) y 2 (a = 1 b = 0), entonces el nuevo valor a ‘= (old_a ^ x) & b, y nuevo valor b ‘= (old_b | x) & b, donde x es la entrada (0 o 1).
Ahora, después de calcular el valor final de ayb, después de procesar cada valor de entrada x, tendremos a’b ‘== 01 o 00 dependiendo de si el número único es 1 o 0, respectivamente. Esto significa que b ‘corresponde al número único.

En esta etapa, suponga que a, b, x son enteros regulares de 32 bits y que las expresiones anteriores siguen siendo válidas, lo que significa que puede ver el valor final de la variable b de 32 bits y ese es el número único.

Suponga que el entero tiene 32 bits.
Podemos extraer cada bit de los números y mantener un contador cuántas veces ha ocurrido ese bit, si el contador no es un múltiplo de 3, establecemos el bit correspondiente en la salida. Al final tenemos nuestra salida.

int res = 0;

para i = 1 a 32
cuenta = 0;
para cada número x en la matriz
si ith bit se establece en x
recuento ++;
if (count% 3) // este bit debe estar en la salida
res | = 1 << i volver res;

En C # esto funciona:

Prueba de clase pública
{
public int onlyOne (puntajes int [])
{
Array.Sort (puntuaciones);
int resultado = 0;
bool x = falso;
para (int i = 0; i {
if (puntajes [i]! = puntajes [i + 2])
{
resultado = puntajes [i];
x = verdadero;
descanso;
}
}
si (x == falso)
puntajes de retorno [puntajes. Longitud – 1];
resultado de retorno;
}
}

Si tienes esta matriz:
int [] a = {1, 1, 1, 2, 3, 3, 3, 56, 56, 56, 2, 2, 89, 78, 78, 78};

Este código devuelve 89.

No estoy seguro si esto es O (n) complejidad de tiempo …
Si no es una respuesta, ¿puede decirme por qué? ¡Puedo aprender mucho! Gracias

usa un mapa hash …
concepto basico
Si el número aparece más de una vez, es 3 veces más, se agregó solo una vez.
Algo:

while (array) {
si el mapa ya contiene el elemento
eliminar el elemento
de lo contrario agregue el elemento
}
el único elemento que queda al final será el que ocurrió solo una vez.
Complejidad de tiempo
la operación de búsqueda es O (1 + k / n)
agregar y eliminar es similar, el peor caso para los 3 es O (n), entonces O (n) + O (n) + O (n) = O (n)
Complejidad espacial
no creo que sea posible hacerlo en O (1) … porque su pregunta no tiene fundamento sin calcular el recuento de cuántas veces aparece cada número … lo que depende básicamente del tamaño de la matriz o de sus datos, no exactamente ser un mapa de tamaño constante
pero el tamaño máximo del mapa hash es N / 3 + 1 donde N es el tamaño de la matriz … pero el mapa hash crece dinámicamente … Y siempre puedes tomar un número aleatorio grande

Recorre todo el número con el código dado

int uno, dos;

dos = dos | (uno y num); // Verifique la posición de bit establecida en lugares pares
uno = uno ^ num; // Verifique la posición del bit establecido en lugares impares

// Este paso es necesario ya que queremos erradicar el conjunto de tres bits
int dup = ~ (uno y dos)
uno = uno y dup
dos = dos y dup

Me hicieron una pregunta similar en la entrevista de Google:
“Se le da una matriz de tamaño n que contiene números del 1 al n – 1, por lo tanto, al menos un número aparece dos veces, encuentre uno de esos números repetidos”

La idea es usar la matriz como índice para almacenar las ocurrencias de los números.

Algoritmo:

1. Comience con index = 0 (elemento inicial) y establezca next_index = index + 1
2. establecer valor = matriz [índice]
3. if value = index: set array [index] = -1 y set index = next_index y set next_index = next_index + 1 y while array [next_index] <0: next_index = next_index + 1
5. más si valor> 0 y matriz [índice] = -1 e índice = valor goto paso2
6. más si valor <0 matriz de impresión [índice]

Para su problema, debe disminuir el valor hasta que sea -3 y después de eso y un escaneo lineal sobre la matriz debería ser suficiente para encontrar el número de ocurrencia único.

Ordene la matriz y busque solo la instancia del elemento.

1) Haga el montón de elementos de la matriz – O (n) tiempo O (1) espacio.

2) En ese montón, todas las claves duplicadas estarán en alguna relación contigua padre-hijo, por lo que todo lo que necesitamos es comenzar desde la raíz (índice 0) y seguir explorando sus elementos secundarios hasta que encontremos 3 ocurrencias de este (tomará buscar hasta un máximo de dos niveles a continuación). Para el elemento con menos de tres ocurrencias, no podremos encontrar 3 elementos con la misma clave dentro de estos 2 niveles.

3) Repita el paso 2 para todos los elementos del índice 0 a n-1 hasta que encontremos la excepción. Esto toma un máximo de O (n) pasos y O (1) espacio también.