Show problems as
Classic problem #3850HardArrayMathDynamic ProgrammingMemoizationNumber Theory

Count Sequences to K

Real-world version: Selections of Throws Scoring Exactly k
Tracked in this browser only
Read Count Sequences to K on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A run of dice throws is given as nums, each a number from 1 to 6.

A selection takes some of the throws, keeping their order, and its score is the product of the throws taken. Two selections are different when they take different positions, even if the throws taken read the same.

Return how many non-empty selections score exactly k.

Examples

Example 1

Input
nums = [2, 3, 4, 6, 1, 5], k = 24
Output
4

Selections scoring 24 include the throws 4 and 6, the throws 2, 3 and 4, and each of those again with the throw of 1 taken as well, since taking it changes nothing about the product but does make a different selection.

Example 2

Input
nums = [1, 1, 1], k = 1
Output
7

Any non-empty selection of throws of one scores one, and there are seven of them.

Example 3

Input
nums = [6], k = 5
Output
0

The only selection scores 6, so nothing scores 5.

Constraints

  • 1 <= nums.length <= 19
  • 1 <= nums[i] <= 6
  • 1 <= k <= 10^15

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_sequences(nums: list[int], k: int) -> int:
Java
public int countSequences(int[] nums, long k)

More on the same topics