-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy path221.py
More file actions
41 lines (31 loc) · 1 KB
/
221.py
File metadata and controls
41 lines (31 loc) · 1 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
"""
Problem:
Let's define a "sevenish" number to be one which is either a power of 7, or the sum of
unique powers of 7. The first few sevenish numbers are 1, 7, 8, 49, and so on. Create
an algorithm to find the nth sevenish number.
"""
def get_nth_sevenish_num(number: int) -> int:
curr = 1
curr_iteration = 1
while curr < number:
curr_iteration += 1
curr += curr_iteration
curr -= curr_iteration
result = 7 ** (curr_iteration - 1)
curr_to_add = 1
for _ in range(number - curr - 1):
result += curr_to_add
curr_to_add *= 7
return result
if __name__ == "__main__":
print(get_nth_sevenish_num(1)) # 1 = 7 ^ 0
print(get_nth_sevenish_num(2)) # 7 = 7 ^ 1
print(get_nth_sevenish_num(3)) # 8 = 7 ^ 0 + 7 ^ 1
print(get_nth_sevenish_num(4)) # 49 = 7 ^ 2
print(get_nth_sevenish_num(5)) # 50 = 7 ^ 0 + 7 ^ 2
print(get_nth_sevenish_num(6)) # 57 = 7 ^ 0 + 7 ^ 1 + 7 ^ 2
"""
SPECS:
TIME COMPLEXITY: O(log(n))
SPACE COMPLEXITY: O(1)
"""