Count Even Numbers

Q: 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, até mesmo em linguagens nas quais -3 % 2 é -1 . Você também pode verificar o bit menos significativo com (x & 1) == 0 .

Q: Zero é um número par?

Sim. Zero dividido por 2 é 0 , sem resto, então se encaixa na definição de número par. Ele também fica entre os números ímpares -1 e 1 , onde um número par se encaixa.

Q: Qual é a complexidade de tempo para contar números pares em um array?

Uma passagem com um contador leva tempo O(n) e usa espaço extra O(1) . Todos os valores precisam ser verificados, então nenhum método é mais rápido que O(n) .

InicianteArrays e strings Matemática e simulação

+10

Dada uma lista não vazia de números inteiros nums, retorne quantos de seus valores são pares. Um número é par quando, ao dividi-lo por 2, não há resto, o que inclui 0 e números negativos, como -4.

Função

countEvens(nums: integer-array) → integer

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
-10⁹ ≤ nums[i] ≤ 10⁹

Exemplos

Entrada: nums = [3, 8, 12, 5, 6]
Saída: 3
Explicação: 8, 12 e 6 são divisíveis por 2 sem deixar resto; 3 e 5 não são. A resposta é 3.

Entrada: nums = [-4, -3, 0, 7]
Saída: 2
Explicação: -4 = 2 × (-2) e 0 = 2 × 0, portanto ambos são pares. -3 e 7 são ímpares, e a contagem é 2.

Entrada: nums = [1, 9, 15]
Saída: 0
Explicação: 1, 9 e 15 são todos ímpares, então a resposta é 0.

Para ir além

Você recebe muitas perguntas: quantos valores pares existem entre o índice l e o índice r? Depois de uma passagem por nums, você consegue responder a cada uma em tempo O(1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Verifique cada valor uma vez e conte aqueles cujo resto é 0 quando divididos por 2. Comparar o resto com 0, em vez de testar se é ímpar com 1, funciona corretamente com números negativos.

Reúna os valores pares e, em seguida, conte-os

Intuição

Selecione os valores pares com um filtro e, em seguida, retorne o comprimento do resultado. Para [3, 8, 12, 5, 6], a lista filtrada é [8, 12, 6], então a resposta é 3.

O tempo é O(n), mas a nova lista custa O(n) de memória, para até 5000 valores, apenas para ler seu comprimento uma vez.

Algoritmo

Crie uma nova lista contendo cada x em nums para o qual x % 2 == 0.
Retorne o tamanho dessa lista.

def countEvens(nums):
    evens = [x for x in nums if x % 2 == 0]
    return len(evens)

Conte com um contador progressivo

Intuição

Mantenha um contador em vez de uma lista e some 1 para cada valor que satisfaça x % 2 == 0. Um número par deixa resto 0, qualquer que seja o seu sinal, então o teste funciona para -4 e 0 em todas as linguagens. Um teste para ímpares escrito como x % 2 == 1 não funciona: em C, Java, JavaScript e na maioria das linguagens semelhantes a C, o resto tem o sinal do número, então -3 % 2 é -1.

Uma passagem e um inteiro: tempo O(n), espaço O(1).

Algoritmo

Defina count como 0.
Percorra cada valor x em nums.
Se x % 2 == 0, adicione 1 a count.
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

Contar os valores ímpares com x % 2 == 1 e subtrair da quantidade de elementos. Em linguagens semelhantes a C, -3 % 2 é -1, então [-3] retorna 1 em vez de 0.
Tratar 0 como não sendo nem par nem ímpar. 0 = 2 × 0, então [0] retorna 1.
Escrever o teste de bit como x & 1 == 0. Em C, C++ e JavaScript, == tem precedência maior que &, então isso significa x & (1 == 0), que é sempre 0 e não conta nada. Escreva (x & 1) == 0.

Perguntas frequentes3

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, até mesmo em linguagens nas quais -3 % 2 é -1. Você também pode verificar o bit menos significativo com (x & 1) == 0.

Zero é um número par?

Sim. Zero dividido por 2 é 0, sem resto, então se encaixa na definição de número par. Ele também fica entre os números ímpares -1 e 1, onde um número par se encaixa.

Qual é a complexidade de tempo para contar números pares em um array?

Uma passagem com um contador leva tempo O(n) e usa espaço extra O(1). Todos os valores precisam ser verificados, então nenhum método é mais rápido que O(n).

def countEvens(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

nums = [3, 8, 12, 5, 6]

Saída Esperada