#008 Producto en Serie

1 Entendiendo el Problema

Tenemos un número gigante de 1000 dígitos. Debemos encontrar 13 dígitos consecutivos cuyo producto sea máximo. La clave: un solo cero arruina todo el producto.

El número de 1000 dígitos:

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Estrategia manual:

1

Identificar los ceros

Cualquier ventana con un cero tiene producto = 0. Marcamos los ceros en rojo para evitarlos.

2

Buscar dígitos grandes consecutivos

Queremos 9s, 8s, 7s consecutivos. 9 × 9 × 9 = 729 vs 2 × 2 × 2 = 8

3

Calcular productos candidatos

Probamos algunas secuencias prometedoras: 9781797784617...

Ventana deslizante visual:

Posición: 0 Producto: 0

Respuesta

23,514,624,000

Dígitos

5576689664895

2 Fuerza Bruta - 3 Variantes

El enfoque directo: probar todas las ventanas de 13 dígitos y calcular el producto de cada una.

Variante A: while True + break

Iteramos con índice manual hasta el final del string.

Python

NUMBER = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace("\n", "")

max_product = 0
i = 0

while True:
    if i > len(NUMBER) - 13:
        break

    window = NUMBER[i:i+13]

    product = 1
    for digit in window:
        product *= int(digit)

    if product > max_product:
        max_product = product
        best_window = window

    i += 1

print(f"Producto máximo: {max_product}")
print(f"Dígitos: {best_window}")

// Output aparecerá aquí

Variante B: while condición

Condición directa en el while.

Python

NUMBER = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace("\n", "")

max_product = 0
best_window = ""
pos = 0

while pos <= len(NUMBER) - 13:
    window = NUMBER[pos:pos+13]

    product = 1
    for d in window:
        product *= int(d)

    if product > max_product:
        max_product = product
        best_window = window

    pos += 1

print(f"Producto máximo: {max_product}")
print(f"Dígitos: {best_window}")

// Output aparecerá aquí

Variante C: for range

Usando range para iterar posiciones.

Python

NUMBER = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace("\n", "")

def product_of_digits(s):
    result = 1
    for char in s:
        result *= int(char)
    return result

max_product = 0
best_window = ""

for i in range(len(NUMBER) - 12):
    window = NUMBER[i:i+13]
    p = product_of_digits(window)

    if p > max_product:
        max_product = p
        best_window = window

print(f"Producto máximo: {max_product}")
print(f"Dígitos: {best_window}")

// Output aparecerá aquí

Análisis de complejidad

Tiempo

O(n × k)

n = 1000 posiciones, k = 13 dígitos

Espacio

O(1)

Solo variables auxiliares

3 Enfoque Pythónico

Usando math.prod, comprensiones, y max con key function.

Python

from math import prod

NUMBER = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace("\n", "")

# Convertir a lista de enteros una sola vez
digits = [int(d) for d in NUMBER]

# Generar todas las ventanas de 13 dígitos
windows = [digits[i:i+13] for i in range(len(digits) - 12)]

# Encontrar el máximo usando prod
best = max(windows, key=prod)

print(f"Producto máximo: {prod(best)}")
print(f"Dígitos: {''.join(map(str, best))}")

// Output aparecerá aquí

Herramientas usadas

math.prod() — Producto de iterables (Python 3.8+)
max(key=) — Máximo con función de comparación
List comprehension — Generar ventanas
''.join(map()) — Reconstruir string

Alternativa con generador

# Memoria constante con generador
windows = (
    digits[i:i+13]
    for i in range(len(digits) - 12)
)
max(windows, key=prod)

4 Optimización Matemática

La ventana deslizante puede optimizarse: en vez de recalcular 13 multiplicaciones en cada paso, podemos dividir y multiplicar... pero los ceros complican todo.

P(i+1) = P(i) \times d[i+k] / d[i] Actualización de ventana en O(1)... si no hay ceros

d[i] = 0 ⟹ P = 0 Un cero anula todo el producto

Estrategia con ceros

Cuando encontramos un cero, no tiene sentido seguir con esa ventana. Saltamos directamente al siguiente segmento sin ceros:

9870123

Cero en posición 3

____123...

Saltar a posición 4

Python — Ventana optimizada

from math import prod

NUMBER = """
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
""".replace("\n", "")

K = 13  # Tamaño de ventana

def max_product_optimized(s, k):
    """Encuentra el producto máximo de k dígitos consecutivos."""
    digits = [int(c) for c in s]
    n = len(digits)

    max_prod = 0
    best_start = 0

    i = 0
    while i <= n - k:
        # Buscar el siguiente cero en la ventana
        zero_pos = -1
        for j in range(i, i + k):
            if digits[j] == 0:
                zero_pos = j
                break

        if zero_pos != -1:
            # Hay un cero, saltar después de él
            i = zero_pos + 1
            continue

        # No hay ceros, calcular producto
        p = prod(digits[i:i+k])

        if p > max_prod:
            max_prod = p
            best_start = i

        i += 1

    return max_prod, best_start

result, pos = max_product_optimized(NUMBER, K)
print(f"Producto máximo: {result}")
print(f"Dígitos: {NUMBER[pos:pos+K]}")
print(f"Posición: {pos}")

# Contar cuántas ventanas con ceros evitamos
zeros = NUMBER.count('0')
print(f"\nOptimización: {zeros} ceros en el número")
print(f"Ventanas con ceros evitadas: ~{zeros * K}")

// Output aparecerá aquí

Comparación de rendimiento

Método	Complejidad	Operaciones (n=1000, k=13)
Fuerza bruta	O(n × k)	~12,844 multiplicaciones
Con skip de ceros	O(n) amortizado	~8,000 multiplicaciones

Nota sobre división en ventana deslizante

Teóricamente podríamos hacer P_new = P_old / d_out × d_in, pero la división por cero y los errores de punto flotante lo hacen impracticable. La estrategia de saltar segmentos con ceros es más robusta y eficiente en la práctica.

Largest Product in a Series

1 Entendiendo el Problema

El número de 1000 dígitos:

Estrategia manual:

Ventana deslizante visual:

2 Fuerza Bruta - 3 Variantes

Variante A: while True + break

Variante B: while condición

Variante C: for range

Análisis de complejidad

3 Enfoque Pythónico

Herramientas usadas

Alternativa con generador

4 Optimización Matemática

Estrategia con ceros

Comparación de rendimiento

Nota sobre división en ventana deslizante