forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsumming_digits.py
More file actions
48 lines (35 loc) · 1.2 KB
/
summing_digits.py
File metadata and controls
48 lines (35 loc) · 1.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
Summing Digits Power
Find all integers in a range where each digit raised to its positional power
(1-indexed) sums to the number itself (e.g., 89 = 8^1 + 9^2).
Reference: https://en.wikipedia.org/wiki/Perfect_digit-to-digit_invariant
Complexity:
Time: O((high - low) * d) where d is the number of digits
Space: O(result size)
"""
from __future__ import annotations
def sum_dig_pow(low: int, high: int) -> list[int]:
"""Find numbers where digits raised to positional powers equal the number.
Args:
low: Lower bound of the range (inclusive).
high: Upper bound of the range (inclusive).
Returns:
List of matching numbers in the range.
Examples:
>>> sum_dig_pow(1, 10)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> sum_dig_pow(1, 100)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 89]
"""
result = []
for number in range(low, high + 1):
exponent = 1
summation = 0
number_as_string = str(number)
tokens = list(map(int, number_as_string))
for k in tokens:
summation = summation + (k**exponent)
exponent += 1
if summation == number:
result.append(number)
return result