forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathall_factors.py
More file actions
100 lines (79 loc) · 2.25 KB
/
all_factors.py
File metadata and controls
100 lines (79 loc) · 2.25 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
"""
Factor Combinations
Given an integer n, return all possible combinations of its factors
(excluding 1 and n itself in the factorisation).
Reference: https://leetcode.com/problems/factor-combinations/
Complexity:
Time: O(n^(1/2) * log n) (approximate, depends on factor density)
Space: O(log n)
"""
from __future__ import annotations
def get_factors(n: int) -> list[list[int]]:
"""Return all factor combinations of *n* using recursion.
Args:
n: The number to factorise.
Returns:
List of factor lists.
Examples:
>>> get_factors(12)
[[2, 6], [2, 2, 3], [3, 4]]
"""
def _factor(
n: int,
i: int,
combi: list[int],
res: list[list[int]],
) -> list[list[int]]:
while i * i <= n:
if n % i == 0:
res += (combi + [i, int(n / i)],)
_factor(n / i, i, combi + [i], res)
i += 1
return res
return _factor(n, 2, [], [])
def get_factors_iterative1(n: int) -> list[list[int]]:
"""Return all factor combinations using an explicit stack.
Args:
n: The number to factorise.
Returns:
List of factor lists.
Examples:
>>> get_factors_iterative1(12)
[[2, 6], [3, 4], [2, 2, 3]]
"""
todo: list[tuple[int, int, list[int]]] = [(n, 2, [])]
res: list[list[int]] = []
while todo:
n, i, combi = todo.pop()
while i * i <= n:
if n % i == 0:
res += (combi + [i, n // i],)
todo.append((n // i, i, combi + [i]))
i += 1
return res
def get_factors_iterative2(n: int) -> list[list[int]]:
"""Return all factor combinations using a stack-based approach.
Args:
n: The number to factorise.
Returns:
List of factor lists.
Examples:
>>> get_factors_iterative2(12)
[[2, 2, 3], [2, 6], [3, 4]]
"""
ans: list[list[int]] = []
stack: list[int] = []
x = 2
while True:
if x > n // x:
if not stack:
return ans
ans.append(stack + [n])
x = stack.pop()
n *= x
x += 1
elif n % x == 0:
stack.append(x)
n //= x
else:
x += 1