LeetCode-Solutions/Python/count-sequences-to-k.py at master · kamyu104/LeetCode-Solutions · GitHub

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
# Time:  O(3^(n/2))
# Space: O(3^(n/2))

import collections


# dp, meet in the middle
class Solution(object):
    def countSequences(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        LOOKUP = {1:(0, 0, 0), 2:(1, 0, 0), 3:(0, 1, 0), 4:(2, 0, 0), 5:(0, 0, 1), 6:(1, 1, 0)}
        def factors(x):
            cnt2 = 0
            while x%2 == 0:
                x //= 2
                cnt2 += 1
            cnt3 = 0
            while x%3 == 0:
                x //= 3
                cnt3 += 1
            cnt5 = 0
            while x%5 == 0:
                x //= 5
                cnt5 += 1
            return (cnt2, cnt3, cnt5) if x == 1 else (-1, -1, -1)

        def count(nums):
            dp = collections.defaultdict(int)
            dp[0, 0, 0] = 1
            for x in nums:
                new_dp = collections.defaultdict(int)
                d2, d3, d5 = LOOKUP[x]
                for (c2, c3, c5), c in dp.iteritems():
                    new_dp[c2, c3, c5] += c
                    new_dp[c2+d2, c3+d3, c5+d5] += c
                    new_dp[c2-d2, c3-d3, c5-d5] += c
                dp = new_dp
            return dp

        c2, c3, c5 = factors(k)
        if c2 == -1:
            return 0
        left = count(nums[:len(nums)//2])
        right = count(nums[len(nums)//2:])
        return sum(d*right[c2-d2, c3-d3, c5-d5] for (d2, d3, d5), d in left.iteritems())


# Time:  O(3^n)
# Space: O(3^n)
import collections


# dp
class Solution2(object):
    def countSequences(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        LOOKUP = {1:(0, 0, 0), 2:(1, 0, 0), 3:(0, 1, 0), 4:(2, 0, 0), 5:(0, 0, 1), 6:(1, 1, 0)}
        def factors(x):
            cnt2 = 0
            while x%2 == 0:
                x //= 2
                cnt2 += 1
            cnt3 = 0
            while x%3 == 0:
                x //= 3
                cnt3 += 1
            cnt5 = 0
            while x%5 == 0:
                x //= 5
                cnt5 += 1
            return (cnt2, cnt3, cnt5) if x == 1 else (-1, -1, -1)

        def count(nums):
            dp = collections.defaultdict(int)
            dp[0, 0, 0] = 1
            for x in nums:
                new_dp = collections.defaultdict(int)
                d2, d3, d5 = LOOKUP[x]
                for (c2, c3, c5), c in dp.iteritems():
                    new_dp[c2, c3, c5] += c
                    new_dp[c2+d2, c3+d3, c5+d5] += c
                    new_dp[c2-d2, c3-d3, c5-d5] += c
                dp = new_dp
            return dp

        c2, c3, c5 = factors(k)
        if c2 == -1:
            return 0
        dp = count(nums)
        return dp[c2, c3, c5]