1class Solution {
2
3    /**
4     * Represents a memoization state during the DFS.
5     *
6     * @param index     the current index into the nums array
7     * @param numerator the numerator of the running product/quotient (in lowest terms)
8     * @param denominator the denominator of the running product/quotient (in lowest terms)
9     */
10    record State(int index, long numerator, long denominator) {
11    }
12
13    // Memoization table mapping a state to the number of valid sequences from that state
14    private Map<State, Integer> memo;
15    // Input array of numbers
16    private int[] nums;
17    // Length of the nums array
18    private int n;
19    // Target value the final product/quotient must equal
20    private long k;
21
22    /**
23     * Counts the number of sequences (choices of multiply, divide, or skip for each
24     * element) whose resulting fraction equals k (i.e. numerator == k and denominator == 1).
25     *
26     * @param nums the array of numbers to operate on
27     * @param k    the target value
28     * @return the number of valid sequences
29     */
30    public int countSequences(int[] nums, long k) {
31        this.nums = nums;
32        this.n = nums.length;
33        this.k = k;
34        this.memo = new HashMap<>();
35        // Start the search from index 0 with fraction 1/1
36        return dfs(0, 1L, 1L);
37    }
38
39    /**
40     * Depth-first search exploring all ways to combine the remaining elements.
41     *
42     * @param index       the current index being processed
43     * @param numerator   the current numerator (already reduced)
44     * @param denominator the current denominator (already reduced)
45     * @return the number of valid sequences reachable from this state
46     */
47    private int dfs(int index, long numerator, long denominator) {
48        // Base case: all elements processed, check whether the fraction equals k
49        if (index == n) {
50            return (numerator == k && denominator == 1L) ? 1 : 0;
51        }
52
53        // Return the cached result if this state was computed before
54        State key = new State(index, numerator, denominator);
55        if (memo.containsKey(key)) {
56            return memo.get(key);
57        }
58
59        // Option 1: skip the current element, keeping the fraction unchanged
60        int result = dfs(index + 1, numerator, denominator);
61
62        long value = nums[index];
63
64        // Option 2: multiply by the current element, then reduce the fraction
65        long gcdMultiply = gcd(numerator * value, denominator);
66        result += dfs(index + 1, (numerator * value) / gcdMultiply, denominator / gcdMultiply);
67
68        // Option 3: divide by the current element, then reduce the fraction
69        long gcdDivide = gcd(numerator, denominator * value);
70        result += dfs(index + 1, numerator / gcdDivide, (denominator * value) / gcdDivide);
71
72        // Cache and return the total count for this state
73        memo.put(key, result);
74        return result;
75    }
76
77    /**
78     * Computes the greatest common divisor of two non-negative longs using the
79     * iterative Euclidean algorithm.
80     *
81     * @param a the first value
82     * @param b the second value
83     * @return the greatest common divisor of a and b
84     */
85    private long gcd(long a, long b) {
86        while (b != 0) {
87            long remainder = a % b;
88            a = b;
89            b = remainder;
90        }
91        return a;
92    }
93}
94

1class Solution {
2public:
3    int size;                                          // total number of elements in nums
4    long long target;                                  // the target product k
5    vector<int>* values;                               // pointer to the input array
6    map<tuple<int, long long, long long>, int> memo;   // memoization: (index, numerator, denominator) -> count
7
8    int countSequences(vector<int>& nums, long long k) {
9        this->values = &nums;
10        this->size = nums.size();
11        this->target = k;
12        memo.clear();
13        // Start the DFS at index 0 with product represented as fraction 1/1
14        return dfs(0, 1LL, 1LL);
15    }
16
17    // dfs explores all subsequences, tracking the running product as a reduced fraction p/q.
18    // i: current index; p: numerator; q: denominator.
19    int dfs(int i, long long p, long long q) {
20        // Base case: all elements processed.
21        // A valid sequence has product exactly k (p == target and q == 1).
22        if (i == size) {
23            return (p == target && q == 1LL) ? 1 : 0;
24        }
25
26        // Return cached result if this state was already computed.
27        auto key = make_tuple(i, p, q);
28        if (memo.count(key)) return memo[key];
29
30        // Choice 1: skip the current element.
31        int result = dfs(i + 1, p, q);
32
33        long long x = (*values)[i];
34
35        // Choice 2: multiply the current element into the product (numerator * x),
36        // then reduce the fraction by its gcd to keep p/q in lowest terms.
37        long long gNum = gcd(p * x, q);
38        result += dfs(i + 1, (p * x) / gNum, q / gNum);
39
40        // Choice 3: divide the product by the current element (denominator * x),
41        // then reduce the fraction to keep it in lowest terms.
42        long long gDen = gcd(p, q * x);
43        result += dfs(i + 1, p / gDen, (q * x) / gDen);
44
45        // Cache and return the total count for this state.
46        memo[key] = result;
47        return result;
48    }
49};
50

1// Memoization cache: maps a state key "i,numerator,denominator" to the count of valid sequences.
2const memo = new Map<string, number>();
3
4// Stores the input array and its length so helper functions can access them globally.
5let inputNums: number[] = [];
6let inputLength = 0;
7let targetK = 0;
8
9/**
10 * Computes the greatest common divisor of two non-negative integers
11 * using the iterative Euclidean algorithm.
12 */
13function gcd(a: number, b: number): number {
14    while (b !== 0) {
15        const remainder = a % b;
16        a = b;
17        b = remainder;
18    }
19    return a;
20}
21
22/**
23 * Depth-first search that explores every element starting from index `i`,
24 * tracking the running product expressed as the reduced fraction
25 * `numerator / denominator`.
26 *
27 * At each element we have three choices:
28 *   1. Skip the element entirely.
29 *   2. Multiply the current value by the element (numerator * x).
30 *   3. Divide the current value by the element (denominator * x).
31 *
32 * A sequence is valid when, after processing all elements, the fraction
33 * equals exactly `targetK` (numerator === k and denominator === 1).
34 */
35function dfs(i: number, numerator: number, denominator: number): number {
36    // Base case: all elements processed.
37    if (i === inputLength) {
38        return numerator === targetK && denominator === 1 ? 1 : 0;
39    }
40
41    // Return the cached result if this state has already been computed.
42    const key = `${i},${numerator},${denominator}`;
43    if (memo.has(key)) {
44        return memo.get(key)!;
45    }
46
47    // Choice 1: skip the current element.
48    let result = dfs(i + 1, numerator, denominator);
49
50    const x = inputNums[i];
51
52    // Choice 2: multiply the fraction by x, then reduce it.
53    const gcdMultiply = gcd(numerator * x, denominator);
54    result += dfs(
55        i + 1,
56        (numerator * x) / gcdMultiply,
57        denominator / gcdMultiply,
58    );
59
60    // Choice 3: divide the fraction by x (multiply denominator), then reduce it.
61    const gcdDivide = gcd(numerator, denominator * x);
62    result += dfs(
63        i + 1,
64        numerator / gcdDivide,
65        (denominator * x) / gcdDivide,
66    );
67
68    // Cache and return the total count for this state.
69    memo.set(key, result);
70    return result;
71}
72
73/**
74 * Counts the number of subsequences whose product (allowing each chosen
75 * element to either multiply or divide the running value) equals `k`.
76 */
77function countSequences(nums: number[], k: number): number {
78    // Initialize global state for the helper functions.
79    inputNums = nums;
80    inputLength = nums.length;
81    targetK = k;
82    memo.clear();
83
84    // Start the search at index 0 with the fraction 1/1.
85    return dfs(0, 1, 1);
86}
87