Count Sequences to K - Solution & Explanation

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:

Example 2:

Example 3:

 

Constraints:

• 1 <= nums.length <= 19
• 1 <= nums[i] <= 6
• 1 <= k <= 1015