Todos os desafios
Médio 1 resolvido 100.0% de aceitação

Largest Adjacent-Digit Product

Take every contiguous window of span digits and multiply its digits.

O que você vai aprender

  • Examinar cada janela de tamanho fixo
  • Multiplicar os dígitos de uma janela
  • Acompanhar o melhor produto

Problema

Take every contiguous window of span digits and multiply its digits. Return the largest product. Leading zeros are ordinary digits; a window containing zero has product zero. Do not reorder or skip digits.

Implement largest_adjacent_digit_product(digits, span).

Input

digits: The digit sequence, including any leading zeros.

span: The exact number of adjacent digits in a window.

Output

Return the greatest product over all windows of this width.

Restrições

1 ≤ digit-string length ≤ 100,000. Characters are 0…9. 1 ≤ span ≤ min(18, length). All products fit signed 64-bit.

Exemplos

Exemplo 1
Entrada:
digits = "23405"
span = 2

Saída esperada:
expected = 12
Entrada:
std::string digits = "23405";
long long span = 2;

Saída esperada:
long long expected = 12;
Entrada:
string digits = "23405";
long span = 2;

Saída esperada:
long expected = 12;

Explicação

The windows 23, 34, 40, and 05 have products 6, 12, 0, and 0. The largest is 12.

Exemplo 2
Entrada:
digits = "102"
span = 3

Saída esperada:
expected = 0
Entrada:
std::string digits = "102";
long long span = 3;

Saída esperada:
long long expected = 0;
Entrada:
string digits = "102";
long span = 3;

Saída esperada:
long expected = 0;

Explicação

There is only one width-three window. It contains zero, so 1 × 0 × 2 = 0.

Como abordar

Tente sozinho primeiro e depois abra uma dica de cada vez.

Dica 1

Um zero dentro de uma janela zera esse produto, então só trechos contíguos sem zero podem contribuir para o máximo.

Dica 2

Use uma janela deslizante ou acompanhe produtos em blocos de dígitos para evitar recalcular cada intervalo do zero.

Dica 3

Observe bem o tamanho exato do trecho: zeros à esquerda contam como dígitos, e se o span ultrapassar um bloco sem zero, o produto é zero.

Complexidade esperada

tempo O(n), espaço extra O(1)

Referências

Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

# Programador Linguagem Tempo Memória Avaliação da IA Solução
1 ННикита Python 975 ms - 4/5 Ver código

Aprenda com outros

Soluções da comunidade

Atenção: 1 solução completa abaixo Tente resolver sozinho primeiro. Você ainda pode espiar o código de outros desenvolvedores e as avaliações da IA. Entre e resolva o desafio para participar da discussão.