Count Even Numbers
Você recebe uma lista não vazia de números inteiros nums. Retorne quantos de seus valores são pares. Um número é par quando dividi-lo por 2 não deixa resto, o que inclui 0 e números negativos, como -4.
Função
- numsinteger-array
- a lista de números inteiros a verificar
- Retornainteger
- o número de valores pares em nums
Restrições
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
Exemplos
- Entrada
- nums = [3, 8, 12, 5, 6]
- Saída
- 3
- Explicação
8,12e6são divisíveis por2sem deixar resto, enquanto3e5deixam resto. Isso faz com que3valores sejam pares.
- Entrada
- nums = [-4, -3, 0, 7]
- Saída
- 2
- Explicação
-4 = 2 × (-2)e0 = 2 × 0, então ambos são pares.-3e7são ímpares, e a quantidade é2.
- Entrada
- nums = [1, 9, 15]
- Saída
- 0
- Explicação
1,9e15são todos ímpares, então nenhum valor conta e a resposta é0.
+12 testes ocultos ao enviar
Para ir além
Você recebe muitas perguntas do tipo: quantos valores pares estão entre o índice l e o índice r? Após uma única passagem por nums, você consegue responder a cada pergunta em tempo O(1)?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
O que sobra quando você divide um número par por
2?Um valor
xé par exatamente quandox % 2é0. Atenção: para um número ímpar negativo, algumas linguagens retornam-1como resto, e não1.Inicie um contador em
0, leia cada valor uma vez e adicione1sempre que o resto da divisão por2for0.
Solução
O loop ocupa uma linha; é no teste de paridade que as soluções falham. Em muitas linguagens, o resto de um número negativo é negativo, então -3 % 2 é -1. Testar x % 2 == 0 funciona para qualquer sinal em qualquer linguagem, e um contador incremental não precisa de memória extra.
Coletar os valores pares e, em seguida, contá-los
Intuição
Divida a tarefa em duas etapas: selecione os valores pares e, em seguida, conte quantos foram selecionados. Um valor x é par quando x % 2 == 0. A maioria das linguagens tem uma função de filtro que cria a nova lista em uma única linha, e o comprimento dela é a resposta. Para [3, 8, 12, 5, 6], a lista filtrada é [8, 12, 6], então a resposta é 3.
Isso está correto e é fácil de ler, mas a nova lista consome O(n) de memória, até 5000 valores aqui, apenas para que seu comprimento seja consultado uma vez. Os próprios valores nunca são usados novamente.
Algoritmo
- Crie uma nova lista contendo cada
xemnumspara o qualx % 2 == 0. - Retorne o comprimento dessa lista.
def countEvens(nums):
evens = [x for x in nums if x % 2 == 0]
return len(evens)Conte com um contador contínuo
Intuição
Mantenha um contador em vez de uma lista. Comece com 0, examine cada valor uma vez e adicione 1 quando o valor for par. Cada valor é verificado exatamente uma vez, então a contagem é exata, e a única memória usada é um inteiro.
O teste exige cuidado. Em C, C++, Java, C#, JavaScript, Go, Rust, Swift e PHP, o resto mantém o sinal do número, então -3 % 2 é -1, não 1. Um número par deixa resto 0, qualquer que seja o seu sinal, então x % 2 == 0 está sempre correto, enquanto um teste de ímpar escrito como x % 2 == 1 não detecta nenhum número ímpar negativo. Para [-4, -3, 0, 7], os restos são 0, -1, 0 e 1, então o contador termina em 2.
Zero também é contado: 0 % 2 é 0, então 0 é par.
Algoritmo
- Defina
countcomo0. - Percorra cada valor
xemnums. - Se
x % 2 == 0, adicione1acount. - Após o loop, retorne
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
Armadilhas e casos extremos
Os bugs aqui vêm dos números negativos e do zero.
- Contar os valores ímpares com
x % 2 == 1e subtrair o resultado do comprimento. Em linguagens semelhantes a C,-3 % 2é-1, então-3nunca é contado como ímpar e acaba sendo contado como par. - Tratar
0como se não fosse par nem ímpar.0 = 2 × 0, então é par, e[0]retorna1. - Escrever o teste de bits como
x & 1 == 0. Em C, C++ e JavaScript,==tem precedência maior que&, então isso significax & (1 == 0), que é sempre0e não conta nenhum valor. Escreva(x & 1) == 0. - Começar o loop no índice
1em uma linguagem com indexação começando em 0, o que ignora o primeiro valor, ou em0em Lua e R, nas quais o primeiro valor está no índice1.
Perguntas frequentes4
Como verificar se um número é par no código?
Teste se o resto após dividir por 2 é zero: x % 2 == 0. Isso funciona para números positivos, números negativos e zero em todas as linguagens populares. Outra maneira é verificar o bit menos significativo com (x & 1) == 0, já que os números pares terminam com um bit 0.
Zero é um número par?
Sim. Zero dividido por 2 é 0, sem resto, então se encaixa na definição de par. Ele também fica entre os números ímpares -1 e 1, exatamente onde um número par deve ficar.
Por que x % 2 == 1 falha para números negativos?
Em C, C++, Java, C#, JavaScript, Go, Rust, Swift e PHP, o resto mantém o sinal do número que está sendo dividido, então -3 % 2 é -1. Python, Ruby, Dart, Lua e R retornam 1 em vez disso. Testar x % 2 != 0 para ímpar e x % 2 == 0 para par fornece a mesma resposta em todas elas.
Qual é a complexidade de tempo de contar números pares em um array?
Uma passagem com um contador leva tempo O(n) e usa O(1) de espaço extra. Cada valor precisa ser verificado, então nenhum método é mais rápido que O(n). Criar primeiro uma lista filtrada fornece a mesma contagem, mas usa O(n) de memória extra.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
Python
def countEvens(nums):
# Escreva o código aquiCaso 1
Caso 2
Caso 3
Entrada
nums = [3, 8, 12, 5, 6]
Esperado
3