3850. Count Sequences to K Hard
1/**
2 * [3850] Count Sequences to K
3 *
4 * You are given an integer array nums, and an integer k.
5 * 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:
6 *
7 * Multiply val by nums[i].
8 * Divide val by nums[i].
9 * Leave val unchanged.
10 *
11 * After processing all elements, val is considered equal to k only if its final rational value exactly equals k.
12 * Return the count of distinct sequences of choices that result in val == k.
13 * Note: Division is rational (exact), not integer division. For example, 2 / 4 = 1 / 2.
14 *
15 * <strong class="example">Example 1:
16 * <div class="example-block">
17 * Input: <span class="example-io">nums = [2,3,2], k = 6</span>
18 * Output: <span class="example-io">2</span>
19 * Explanation:
20 * The following 2 distinct sequences of choices result in val == k:
21 * <table style="border: 1px solid black;">
22 * <thead>
23 * <tr>
24 * <th style="border: 1px solid black;">Sequence</th>
25 * <th style="border: 1px solid black;">Operation on nums[0]</th>
26 * <th style="border: 1px solid black;">Operation on nums[1]</th>
27 * <th style="border: 1px solid black;">Operation on nums[2]</th>
28 * <th style="border: 1px solid black;">Final val</th>
29 * </tr>
30 * </thead>
31 * <tbody>
32 * <tr>
33 * <td style="border: 1px solid black;">1</td>
34 * <td style="border: 1px solid black;">Multiply: val = 1 * 2 = 2</td>
35 * <td style="border: 1px solid black;">Multiply: val = 2 * 3 = 6</td>
36 * <td style="border: 1px solid black;">Leave val unchanged</td>
37 * <td style="border: 1px solid black;">6</td>
38 * </tr>
39 * <tr>
40 * <td style="border: 1px solid black;">2</td>
41 * <td style="border: 1px solid black;">Leave val unchanged</td>
42 * <td style="border: 1px solid black;">Multiply: val = 1 * 3 = 3</td>
43 * <td style="border: 1px solid black;">Multiply: val = 3 * 2 = 6</td>
44 * <td style="border: 1px solid black;">6</td>
45 * </tr>
46 * </tbody>
47 * </table>
48 * </div>
49 * <strong class="example">Example 2:
50 * <div class="example-block">
51 * Input: <span class="example-io">nums = [4,6,3], k = 2</span>
52 * Output: <span class="example-io">2</span>
53 * Explanation:
54 * The following 2 distinct sequences of choices result in val == k:
55 * <table style="border: 1px solid black;">
56 * <thead>
57 * <tr>
58 * <th style="border: 1px solid black;">Sequence</th>
59 * <th style="border: 1px solid black;">Operation on nums[0]</th>
60 * <th style="border: 1px solid black;">Operation on nums[1]</th>
61 * <th style="border: 1px solid black;">Operation on nums[2]</th>
62 * <th style="border: 1px solid black;">Final val</th>
63 * </tr>
64 * </thead>
65 * <tbody>
66 * <tr>
67 * <td style="border: 1px solid black;">1</td>
68 * <td style="border: 1px solid black;">Multiply: val = 1 * 4 = 4</td>
69 * <td style="border: 1px solid black;">Divide: val = 4 / 6 = 2 / 3</td>
70 * <td style="border: 1px solid black;">Multiply: val = (2 / 3) * 3 = 2</td>
71 * <td style="border: 1px solid black;">2</td>
72 * </tr>
73 * <tr>
74 * <td style="border: 1px solid black;">2</td>
75 * <td style="border: 1px solid black;">Leave val unchanged</td>
76 * <td style="border: 1px solid black;">Multiply: val = 1 * 6 = 6</td>
77 * <td style="border: 1px solid black;">Divide: val = 6 / 3 = 2</td>
78 * <td style="border: 1px solid black;">2</td>
79 * </tr>
80 * </tbody>
81 * </table>
82 * </div>
83 * <strong class="example">Example 3:
84 * <div class="example-block">
85 * Input: <span class="example-io">nums = [1,5], k = 1</span>
86 * Output: <span class="example-io">3</span>
87 * Explanation:
88 * The following 3 distinct sequences of choices result in val == k:
89 * <table style="border: 1px solid black;">
90 * <thead>
91 * <tr>
92 * <th style="border: 1px solid black;">Sequence</th>
93 * <th style="border: 1px solid black;">Operation on nums[0]</th>
94 * <th style="border: 1px solid black;">Operation on nums[1]</th>
95 * <th style="border: 1px solid black;">Final val</th>
96 * </tr>
97 * </thead>
98 * <tbody>
99 * <tr>
100 * <td style="border: 1px solid black;">1</td>
101 * <td style="border: 1px solid black;">Multiply: val = 1 * 1 = 1</td>
102 * <td style="border: 1px solid black;">Leave val unchanged</td>
103 * <td style="border: 1px solid black;">1</td>
104 * </tr>
105 * <tr>
106 * <td style="border: 1px solid black;">2</td>
107 * <td style="border: 1px solid black;">Divide: val = 1 / 1 = 1</td>
108 * <td style="border: 1px solid black;">Leave val unchanged</td>
109 * <td style="border: 1px solid black;">1</td>
110 * </tr>
111 * <tr>
112 * <td style="border: 1px solid black;">3</td>
113 * <td style="border: 1px solid black;">Leave val unchanged</td>
114 * <td style="border: 1px solid black;">Leave val unchanged</td>
115 * <td style="border: 1px solid black;">1</td>
116 * </tr>
117 * </tbody>
118 * </table>
119 * </div>
120 *
121 * Constraints:
122 *
123 * 1 <= nums.length <= 19
124 * 1 <= nums[i] <= 6
125 * 1 <= k <= 10^15
126 *
127 */
128pub struct Solution {}
129
130// problem: https://leetcode.com/problems/count-sequences-to-k/
131// discuss: https://leetcode.com/problems/count-sequences-to-k/discuss/?currentPage=1&orderBy=most_votes&query=
132
133// submission codes start here
134
135impl Solution {
136 pub fn count_sequences(nums: Vec<i32>, k: i64) -> i32 {
137 0
138 }
139}
140
141// submission codes end
142
143#[cfg(test)]
144mod tests {
145 use super::*;
146
147 #[test]
148 fn test_3850() {
149 }
150}
151Back
© 2026 bowen.ge All Rights Reserved.