LeetCode 3850 | Weekly 490.4 Hard | Count Sequences to K

LeetCode 3850. Count Sequences to K

Intuition

The subproblem is, how many steps start from $DP[i,c_2,c_3,c_5]$ to $DP[i+1,c_2,c_3,c_5]$, then find $DP[n, t_2,t_3,t_5]$

This sounds difficult to figure out. Let’s simplify: the target is to calculate steps to mul or divide $nums_i$ to $k$. Here, $k$ is extreme large, but $1\leq nums_i \leq 6$ indicates $ nums_i \in { 1,2,3,4,5,6} $, every number can be factorized into multiplying power of 2, 3 and 5.

So this is the Key Point 1: If you can’t factorize k into 2,3,5, there is no path towards k.

But why DP? You can try BFS/DFS, you will got TLE. So let’s optimize!

Let’s take example from sample 3: [1,5], 1.

the answer is 3, means doing nothing/times1/divide by 1 at first time. Do you want to count 3 times at second value 5? Of course not. then you gonna save this point with weight 3.

Assume you already saved $DP[i,c_2,c_3,c_5] = weight$, then things become easy: just update

\[DP[i+1,n_2,n_3,n_5] = \sum DP[i,c_2,c_3,c_5]\]

i.e., $n_5$ means new value, $n_5 = c_5 + 1$, $+0$ or $-1$ $n_2$ gonna be $+1,+2,0,-1,-2$; $n_3$ gonna be $+1,0,-1$

So this is the Key Point 2: 2,3,5 factor encoding of 1,2,3,4,5,6: i.e., encoding 4 as (2,0,0).

Approach

For C++ version, I use bit operation to show how to make the index, showing recursive DP implement; for python version, I use rolling DP(hashing) method to show non-recursive DP implement.

long long key = ((long long)i << 30) | ((long long)(c2 + 100) << 20) | ((c3 + 100) << 10) | (c5 + 100);

here 100 is the offset to avoid less than 0. Notice that c2,c3,c5 between (-100,100), $(200){10} = (11001000){2}$ so it’s very safe in 10 bits.

If you want to write a non-recursive C++ code, here’re partly details for encoding and decoding

const int OFFSET = 100;
        
        
auto encode = [&](int c2, int c3, int c5) -> long long {
    return ((long long)(c2 + OFFSET) << 20) | 
           ((long long)(c3 + OFFSET) << 10) | 
           (c5 + OFFSET);
};


int c2 = ((key >> 20) & 0x3FF) - OFFSET;
int c3 = ((key >> 10) & 0x3FF) - OFFSET;
int c5 = (key & 0x3FF) - OFFSET;

Complexity

• Time complexity: worst $O(N^4)$ but it’s hard to get; avg $O(S)«O(N^4)$, best case $O(\log{K})$ or $O(N)$

• Space complexity: $O(N^3)$ for nonrecursive , $O(N^4) for recursive$

Code

class Solution {
public:
    int t2 = 0,t3 = 0,t5 = 0;
    unordered_map<long long,int> dp ;
    int solve(vector<int>& nums, long long k, int i, int c2, int c3, int c5){
        if (nums.size()<=i){
            if (c2==t2 && c3==t3 && c5==t5){
                return 1;
            }
            return 0;
        }
        
        long long key = ((long long)i << 30) | ((long long)(c2 + 100) << 20) | ((c3 + 100) << 10) | (c5 + 100);
        if (dp.find(key)!=dp.end()){
            return dp[key];
        }

        int tc2 = (nums[i] == 4)+(nums[i]%2==0), tc3 = (nums[i]%3 == 0), tc5 = (nums[i] == 5);
        int ans = (solve(nums,k,i+1,c2,c3,c5)+solve(nums,k,i+1,c2+tc2,c3+tc3,c5+tc5)+solve(nums,k,i+1,c2-tc2,c3-tc3,c5-tc5));
        return dp[key] = ans;
    }
    int countSequences(vector<int>& nums, long long k) {
        while (k>1){
            if(k%2==0){t2++;k/=2;}
            else if(k%3==0){t3++;k/=3;}
            else if(k%5==0){t5++;k/=5;}
            else{
                return 0;
            }
        }
        return solve(nums,k,0,0,0,0);
        
    } 
};

class Solution:
    def countSequences(self, nums: List[int], k: int) -> int:
        ans = 0
        
        t2, t3, t5 = 0,0,0
        while k>1:
            if k %2 ==0:
                k //=2
                t2 += 1
            elif k %3==0:
                k //=3
                t3 += 1
            elif k %5==0:
                k //= 5
                t5 += 1
            else:
                return 0
        dp, nextdp = {(0,0,0):1}, defaultdict(int)
        for i in nums:
            d2, d3, d5 = int(i==4) + int(0==i%2) , int(i%3==0), int(i==5)
            print(d2,d3,d5)
            for (c2, c3, c5),count in dp.items():
                print((c2, c3, c5))
                nextdp[(c2,c3,c5)]+=count
                nextdp[(c2+d2,c3+d3,c5+d5)]+=count
                nextdp[(c2-d2,c3-d3,c5-d5)]+=count
            print(nextdp)
            dp, nextdp = nextdp, defaultdict(int)
        
        for (c2, c3, c5),count in dp.items():
            if c2==t2 and c3==t3 and c5==t5:
                ans += count
        return ans