3850. Count Sequences to K

Description

You are given an integer array nums, and an integer k.

Start with an initial value val = 1 and process nums from left to right. At each index i, you must choose exactly one of the following actions:

Multiply val by nums[i].
Divide val by nums[i].
Leave val unchanged.

After processing all elements, val is considered equal to k only if its final rational value exactly equals k.

Return the count of distinct sequences of choices that result in val == k.

Note: Division is rational (exact), not integer division. For example, 2 / 4 = 1 / 2.

Example 1:

Input: nums = [2,3,2], k = 6

Output: 2

Explanation:

The following 2 distinct sequences of choices result in val == k:

Sequence	Operation on `nums[0]`	Operation on `nums[1]`	Operation on `nums[2]`	Final `val`
1	Multiply: `val = 1 * 2 = 2`	Multiply: `val = 2 * 3 = 6`	Leave `val` unchanged	6
2	Leave `val` unchanged	Multiply: `val = 1 * 3 = 3`	Multiply: `val = 3 * 2 = 6`	6

Example 2:

Input: nums = [4,6,3], k = 2

Output: 2

Explanation:

The following 2 distinct sequences of choices result in val == k:

Sequence	Operation on `nums[0]`	Operation on `nums[1]`	Operation on `nums[2]`	Final `val`
1	Multiply: `val = 1 * 4 = 4`	Divide: `val = 4 / 6 = 2 / 3`	Multiply: `val = (2 / 3) * 3 = 2`	2
2	Leave `val` unchanged	Multiply: `val = 1 * 6 = 6`	Divide: `val = 6 / 3 = 2`	2

Example 3:

Input: nums = [1,5], k = 1

Output: 3

Explanation:

The following 3 distinct sequences of choices result in val == k:

Sequence	Operation on `nums[0]`	Operation on `nums[1]`	Final `val`
1	Multiply: `val = 1 * 1 = 1`	Leave `val` unchanged	1
2	Divide: `val = 1 / 1 = 1`	Leave `val` unchanged	1
3	Leave `val` unchanged	Leave `val` unchanged	1

Constraints:

1 <= nums.length <= 19
1 <= nums[i] <= 6
1 <= k <= 10¹⁵

Solutions

Solution 1: Memoization Search

We define a function \(\text{dfs}(i, p, q)\) that represents the number of different choice sequences when processing at index \(i\) with the current rational value being \(\frac{p}{q}\). Initially, \(\text{dfs}(0, 1, 1)\) represents starting from the initial value of \(1\).

For each index \(i\), we have three choices:

Keep it unchanged, i.e., \(\text{dfs}(i + 1, p, q)\).
Multiply by \(nums[i]\), i.e., \(\text{dfs}(i + 1, p \cdot nums[i], q)\).
Divide by \(nums[i]\), i.e., \(\text{dfs}(i + 1, p, q \cdot nums[i])\).

To avoid excessively large numbers, we simplify the numerator and denominator after each multiplication or division. Finally, when \(i\) equals \(n\), if \(\frac{p}{q}\) exactly equals \(k\), we return \(1\); otherwise, we return \(0\).

The time complexity is \(O(n^4 + \log k)\), and the space complexity is \(O(n^4)\), where \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScript

class Solution:
    def countSequences(self, nums: List[int], k: int) -> int:
        @cache
        def dfs(i: int, p: int, q: int) -> int:
            if i == n:
                return 1 if p == k and q == 1 else 0
            x = nums[i]
            res = dfs(i + 1, p, q)
            g = gcd(p * x, q)
            res += dfs(i + 1, p * x // g, q // g)
            g = gcd(p, q * x)
            res += dfs(i + 1, p // g, q * x // g)
            return res

        n = len(nums)
        ans = dfs(0, 1, 1)
        dfs.cache_clear()
        return ans

class Solution {

    record State(int i, long p, long q) {
    }

    private Map<State, Integer> f;
    private int[] nums;
    private int n;
    private long k;

    public int countSequences(int[] nums, long k) {
        this.nums = nums;
        this.n = nums.length;
        this.k = k;
        this.f = new HashMap<>();
        return dfs(0, 1L, 1L);
    }

    private int dfs(int i, long p, long q) {
        if (i == n) {
            return (p == k && q == 1L) ? 1 : 0;
        }

        State key = new State(i, p, q);
        if (f.containsKey(key)) {
            return f.get(key);
        }

        int res = dfs(i + 1, p, q);

        long x = nums[i];

        long g1 = gcd(p * x, q);
        res += dfs(i + 1, (p * x) / g1, q / g1);

        long g2 = gcd(p, q * x);
        res += dfs(i + 1, p / g2, (q * x) / g2);

        f.put(key, res);
        return res;
    }

    private long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

class Solution {
public:
    int n;
    long long k;
    vector<int>* nums;
    map<tuple<int, long long, long long>, int> f;

    int countSequences(vector<int>& nums, long long k) {
        this->nums = &nums;
        this->n = nums.size();
        this->k = k;
        f.clear();
        return dfs(0, 1LL, 1LL);
    }

    int dfs(int i, long long p, long long q) {
        if (i == n) {
            return (p == k && q == 1LL) ? 1 : 0;
        }

        auto key = make_tuple(i, p, q);
        if (f.count(key)) return f[key];

        int res = dfs(i + 1, p, q);

        long long x = (*nums)[i];

        long long g1 = gcd(p * x, q);
        res += dfs(i + 1, (p * x) / g1, q / g1);

        long long g2 = gcd(p, q * x);
        res += dfs(i + 1, p / g2, (q * x) / g2);

        f[key] = res;
        return res;
    }
};

func countSequences(nums []int, k int64) int {
    n := len(nums)
    type state struct {
        i int
        p int64
        q int64
    }
    f := make(map[state]int)

    var gcd func(int64, int64) int64
    gcd = func(a, b int64) int64 {
        for b != 0 {
            a, b = b, a%b
        }
        return a
    }

    var dfs func(int, int64, int64) int
    dfs = func(i int, p int64, q int64) int {
        if i == n {
            if p == k && q == 1 {
                return 1
            }
            return 0
        }

        key := state{i, p, q}
        if v, ok := f[key]; ok {
            return v
        }

        res := dfs(i+1, p, q)

        x := int64(nums[i])

        g1 := gcd(p*x, q)
        res += dfs(i+1, (p*x)/g1, q/g1)

        g2 := gcd(p, q*x)
        res += dfs(i+1, p/g2, (q*x)/g2)

        f[key] = res
        return res
    }

    return dfs(0, 1, 1)
}

function countSequences(nums: number[], k: number): number {
    const n = nums.length;
    const f = new Map<string, number>();

    function gcd(a: number, b: number): number {
        while (b !== 0) {
            const t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    function dfs(i: number, p: number, q: number): number {
        if (i === n) {
            return p === k && q === 1 ? 1 : 0;
        }

        const key = `${i},${p},${q}`;
        if (f.has(key)) return f.get(key)!;

        let res = dfs(i + 1, p, q);

        const x = nums[i];

        const g1 = gcd(p * x, q);
        res += dfs(i + 1, (p * x) / g1, q / g1);

        const g2 = gcd(p, q * x);
        res += dfs(i + 1, p / g2, (q * x) / g2);

        f.set(key, res);
        return res;
    }

    return dfs(0, 1, 1);
}

3850. Count Sequences to K

Description

Solutions

Solution 1: Memoization Search

Comments