mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 21:45:27 +08:00
Ankur Kataria
9391f546d6
* perf(project_euler): replace problem_092 sol1 with digit DP The previous solution iterated all 10,000,000 values in a Python-level for-loop (~6 s on GitHub Actions CI). The new approach uses digit DP over the decimal digits of (number-1): counts in O(k * 568 * 10) ~ 40k ops how many integers in [0, number-1] have each digit-square sum, then multiplies by a precomputed lookup of whether each sum eventually reaches 89. Running time on the default input drops from ~6 s to ~0.004 s (~1500x). Closes #8594 * perf(project_euler): replace problem_092/sol1 with digit DP * chore: remove workflow artifact (.oss-upstream)
108 lines
3.8 KiB
Python
108 lines
3.8 KiB
Python
"""
|
|
Project Euler Problem 092: https://projecteuler.net/problem=92
|
|
Square digit chains
|
|
A number chain is created by continuously adding the square of the digits in
|
|
a number to form a new number until it has been seen before.
|
|
For example,
|
|
44 → 32 → 13 → 10 → 1 → 1
|
|
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
|
|
Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop.
|
|
What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.
|
|
How many starting numbers below ten million will arrive at 89?
|
|
|
|
References:
|
|
- https://en.wikipedia.org/wiki/Digital_root
|
|
- https://en.wikipedia.org/wiki/Digit_DP
|
|
"""
|
|
|
|
|
|
def solution(number: int = 10_000_000) -> int:
|
|
"""
|
|
Returns how many starting numbers below `number` will arrive at 89
|
|
in the digit-square chain.
|
|
|
|
Uses digit DP so the count is computed in O(k * d_max * 10) time —
|
|
roughly 40 000 operations for number = 10^7 — instead of iterating
|
|
all `number` values explicitly.
|
|
|
|
Key observations:
|
|
1. For any n < number, digit_square_sum(n) ≤ num_digits * 81,
|
|
so chain endpoints can be precomputed for that small range only.
|
|
2. A digit DP over the decimal digits of (number - 1) counts how many
|
|
integers in [0, number-1] have each possible digit-square sum,
|
|
grouping by whether the prefix is still bounded ("tight") or free.
|
|
Integers whose digit-square sum equals 0 are exactly 0 itself.
|
|
|
|
>>> solution(100)
|
|
80
|
|
|
|
>>> solution(10_000_000)
|
|
8581146
|
|
"""
|
|
num_digits = len(str(number - 1)) if number > 1 else 1
|
|
limit = num_digits * 81 + 1 # max possible digit-square sum + 1
|
|
|
|
def digit_square_sum(n: int) -> int:
|
|
total = 0
|
|
while n:
|
|
total += (n % 10) ** 2
|
|
n //= 10
|
|
return total
|
|
|
|
# Precompute whether each value 1..limit-1 eventually reaches 89.
|
|
# All intermediate chain values stay below limit because the digit-square
|
|
# sum of any k-digit number is at most k * 81 = limit - 1.
|
|
ends_at_89 = bytearray(limit)
|
|
for i in range(1, limit):
|
|
n = i
|
|
while n not in (1, 89):
|
|
n = digit_square_sum(n)
|
|
ends_at_89[i] = n == 89
|
|
|
|
# Digit DP over the decimal digits of (number - 1).
|
|
# Treating shorter numbers as zero-padded strings (e.g. 7 → "0000007")
|
|
# is safe because 0^2 = 0 contributes nothing to the digit-square sum.
|
|
# dp_tight[s] / dp_free[s] = count of digit sequences whose running
|
|
# digit-square sum is s and whose prefix is still ≤ / already < the
|
|
# corresponding prefix of (number - 1).
|
|
digits = [int(d) for d in str(number - 1)] if number > 1 else [0]
|
|
|
|
dp_tight: dict[int, int] = {0: 1}
|
|
dp_free: dict[int, int] = {}
|
|
|
|
for lim in digits:
|
|
new_tight: dict[int, int] = {}
|
|
new_free: dict[int, int] = {}
|
|
|
|
for dss, cnt in dp_tight.items():
|
|
for d in range(lim + 1):
|
|
new_val = dss + d * d
|
|
if new_val < limit:
|
|
if d == lim:
|
|
new_tight[new_val] = new_tight.get(new_val, 0) + cnt
|
|
else:
|
|
new_free[new_val] = new_free.get(new_val, 0) + cnt
|
|
|
|
for dss, cnt in dp_free.items():
|
|
for d in range(10):
|
|
new_val = dss + d * d
|
|
if new_val < limit:
|
|
new_free[new_val] = new_free.get(new_val, 0) + cnt
|
|
|
|
dp_tight, dp_free = new_tight, new_free
|
|
|
|
# Sum counts for all digit-square sums that end at 89.
|
|
# dss == 0 corresponds to the number 0, which is excluded.
|
|
return sum(
|
|
cnt
|
|
for dss, cnt in (*dp_tight.items(), *dp_free.items())
|
|
if 0 < dss < limit and ends_at_89[dss]
|
|
)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod()
|
|
print(f"{solution() = }")
|