Count Even Numbers
Recibes una lista no vacía de números enteros nums. Devuelve cuántos de sus valores son pares. Un número es par cuando al dividirlo entre 2 no queda ningún resto, lo que incluye 0 y números negativos como -4.
Función
- numsinteger-array
- la lista de números enteros que se deben comprobar
- Devuelveinteger
- el número de valores pares en nums
Restricciones
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Ejemplos
- Entrada
- nums = [3, 8, 12, 5, 6]
- Salida
- 3
- Explicación
8,12y6se dividen entre2sin que sobre nada, mientras que3y5dejan un resto. Eso hace que haya3valores pares.
- Entrada
- nums = [-4, -3, 0, 7]
- Salida
- 2
- Explicación
-4 = 2 × (-2)y0 = 2 × 0, así que ambos son pares.-3y7son impares, y la cantidad es2.
- Entrada
- nums = [1, 9, 15]
- Salida
- 0
- Explicación
1,9y15son todos impares, así que ningún valor cuenta y la respuesta es0.
+12 pruebas ocultas al enviar
Para ir más allá
Recibes muchas preguntas de este tipo: ¿cuántos valores pares hay entre el índice l y el índice r? Después de recorrer nums una vez, ¿puedes responder cada pregunta en tiempo O(1)?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
¿Qué queda cuando divides un número par entre
2?Un valor
xes par exactamente cuandox % 2es0. Ten cuidado: para un número impar negativo, algunos lenguajes dan-1como resto, no1.Inicia un contador en
0, lee cada valor una vez y suma1cada vez que el resto al dividir entre2sea0.
Solución
El bucle ocupa una línea; la prueba de paridad es donde fallan las soluciones. En muchos lenguajes, el resto de un número negativo es negativo, así que -3 % 2 es -1. Comprobar x % 2 == 0 es correcto para cualquier signo en todos los lenguajes, y un contador acumulado no necesita memoria adicional.
Recopila los valores pares y después cuéntalos
Intuición
Divide la tarea en dos pasos: selecciona los valores pares y después cuenta los que seleccionaste. Un valor x es par cuando x % 2 == 0. La mayoría de los lenguajes tienen una función de filtrado que crea la nueva lista en una sola línea, y su longitud es la respuesta. Para [3, 8, 12, 5, 6], la lista filtrada es [8, 12, 6], así que la respuesta es 3.
Esto es correcto y se lee bien, pero la nueva lista requiere memoria O(n), hasta 5000 valores en este caso, solo para leer su longitud una vez. Los valores en sí no se vuelven a usar.
Algoritmo
- Crea una nueva lista que contenga cada
xdenumspara el quex % 2 == 0. - Devuelve la longitud de esa lista.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Cuenta con un contador acumulativo
Intuición
Usa un contador en lugar de una lista. Inicialízalo en 0, examina cada valor una sola vez y suma 1 cuando el valor sea par. Cada valor se comprueba exactamente una vez, así que el recuento es exacto y la única memoria que se necesita es un entero.
La comprobación requiere cuidado. En C, C++, Java, C#, JavaScript, Go, Rust, Swift y PHP, el resto conserva el signo del número, así que -3 % 2 es -1, no 1. Un número par deja un resto de 0 independientemente de su signo, así que x % 2 == 0 siempre es correcto, mientras que una comprobación de impar escrita como x % 2 == 1 no detecta ningún número impar negativo. Para [-4, -3, 0, 7], los restos son 0, -1, 0 y 1, así que el contador termina en 2.
El cero también cuenta: 0 % 2 es 0, así que 0 es par.
Algoritmo
- Establece
counten0. - Recorre cada valor
xennums. - Si
x % 2 == 0, suma1acount. - Después del bucle, devuelve
count.
def countEvens(nums):
count = 0
for x in nums:
if x % 2 == 0: # 0 also works for negatives, where the remainder can be -1
count += 1
return count
Errores comunes y casos límite
Los errores aquí provienen de los números negativos y del cero.
- Contar los valores impares con
x % 2 == 1y restar el resultado de la longitud. En los lenguajes similares a C,-3 % 2es-1, así que-3nunca se cuenta como impar y termina contándose como par. - Tratar el
0como si no fuera ni par ni impar.0 = 2 × 0, así que es par, y[0]devuelve1. - Escribir la prueba de bits como
x & 1 == 0. En C, C++ y JavaScript,==tiene mayor precedencia que&, así que significax & (1 == 0), que siempre es0y no cuenta nada. Escribe(x & 1) == 0. - Iniciar el bucle en el índice
1en un lenguaje indexado desde0, lo que omite el primer valor, o en0en Lua y R, donde el primer valor está en el índice1.
Preguntas frecuentes4
¿Cómo compruebas si un número es par en el código?
Comprueba si el resto después de dividir por 2 es cero: x % 2 == 0. Esto funciona con números positivos, números negativos y cero en todos los lenguajes principales. Otra forma es comprobar el bit menos significativo con (x & 1) == 0, ya que los números pares terminan en un bit 0.
¿Cero es un número par?
Sí. Cero dividido entre 2 es 0 sin resto, así que cumple la definición de par. También se encuentra entre los números impares -1 y 1, exactamente donde corresponde un número par.
¿Por qué falla x % 2 == 1 con números negativos?
En C, C++, Java, C#, JavaScript, Go, Rust, Swift y PHP, el resto toma el signo del número que se divide, así que -3 % 2 es -1. Python, Ruby, Dart, Lua y R devuelven 1 en su lugar. Comprobar x % 2 != 0 para los números impares y x % 2 == 0 para los pares da la misma respuesta en todos ellos.
¿Cuál es la complejidad temporal de contar los números pares en un array?
Una pasada con un contador tarda O(n) y usa O(1) de espacio adicional. Hay que comprobar cada valor, así que ningún método es más rápido que O(n). Crear primero una lista filtrada da el mismo recuento, pero usa O(n) de memoria adicional.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def countEvens(nums):
# Escribe el código aquíCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 8, 12, 5, 6]
Esperado
3