LeetCode 3850 - Count Sequences to K

We start with a value val = 1 and process the array from left to right. For every element nums[i], we must choose exactly one of three actions: - Multiply the current value by nums[i] - Divide the current value by nums[i] - Do nothing Division is exact rational division, not…

leetcodehardarraymathdynamic-programmingmemoizationnumber-theory

LeetCode Problem 3850

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Memoization, Number Theory

Solution

LeetCode 3850 - Count Sequences to K

Problem Understanding

We start with a value val = 1 and process the array from left to right.

For every element nums[i], we must choose exactly one of three actions:

  • Multiply the current value by nums[i]
  • Divide the current value by nums[i]
  • Do nothing

Division is exact rational division, not integer division. This means intermediate and final values may be fractions. For example:

  • 1 / 2 = 1/2
  • (1/2) * 6 = 3

After all elements have been processed, we count the sequence of choices if and only if the final rational value is exactly equal to k.

The task is to return the number of distinct choice sequences that produce k.

The constraints are very important:

  • n <= 19
  • nums[i] <= 6
  • k <= 10^15

A naive solution would examine all possible action sequences. Since each position has three choices, that gives 3^n possibilities.

For n = 19:

$$3^{19} = 1,162,261,467$$

which is far too large.

The key observation comes from the small value range of nums[i].

Since every number is at most 6, its prime factorization only contains the primes:

  • 2
  • 3
  • 5

Specifically:

Number Prime Exponents (2,3,5)
1 (0,0,0)
2 (1,0,0)
3 (0,1,0)
4 (2,0,0)
5 (0,0,1)
6 (1,1,0)

Multiplication adds prime exponents.

Division subtracts prime exponents.

Therefore the entire process can be represented as adding vectors in a 3-dimensional exponent space.

Important edge cases include:

  • k containing a prime factor larger than 5. Such a value can never be produced because every operation only changes exponents of 2, 3, and 5.
  • Arrays containing many 1s. Multiplying or dividing by 1 does not change the value, but the choices are still distinct and must be counted separately.
  • k = 1, where the target exponent vector is (0,0,0).
  • Large exponents in k. If the required exponent exceeds what all numbers together can contribute, the answer is automatically zero.

Approaches

Brute Force

The most direct approach is to try every possible action sequence.

For each position:

  • choose multiply
  • choose divide
  • choose nothing

We simulate the resulting rational value and count how many sequences end at k.

This is correct because every valid sequence is examined exactly once.

Unfortunately, there are 3^n sequences.

For n = 19, this exceeds one billion possibilities and is completely impractical.

Key Insight

Instead of tracking rational numbers directly, track prime exponents.

Every operation only affects exponents of:

  • 2
  • 3
  • 5

Let each number contribute a vector:

$$(a,b,c)$$

representing its exponents of (2,3,5).

Then:

  • multiply → add the vector
  • divide → subtract the vector
  • unchanged → add (0,0,0)

The final exponent vector must equal the exponent vector of k.

Now the problem becomes:

Count assignments of values {-1,0,+1} to every vector such that the resulting vector sum equals the target vector.

Since n ≤ 19, a meet-in-the-middle solution is ideal.

Split the array into two halves.

Enumerate all states in each half:

$$3^{10} = 59049$$

which is manageable.

Store all vector sums from the left half, then find complementary sums from the right half.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(3^n) O(n) Enumerates every action sequence
Optimal Meet-in-the-Middle O(3^(n/2)) O(3^(n/2)) Uses exponent vectors and frequency counting

Algorithm Walkthrough

Step 1: Factorize k

Extract exponents of:

  • 2
  • 3
  • 5

from k.

If any factor remains afterward, then k contains a prime larger than 5 and the answer is immediately 0.

The resulting exponent tuple becomes the target vector.

Step 2: Convert Each Number Into an Exponent Vector

For every value in nums, compute:

$$(e_2,e_3,e_5)$$

Examples:

  • 2 → (1,0,0)
  • 4 → (2,0,0)
  • 6 → (1,1,0)

These vectors completely describe how the number affects prime exponents.

Step 3: Split the Array

Divide the vectors into two halves:

  • left half
  • right half

Each half contains at most 10 elements.

Step 4: Enumerate All Left-Half States

Use DFS.

For every element there are three choices:

  • add vector
  • subtract vector
  • ignore vector

Record the resulting exponent sum.

Store:

sum_vector -> frequency

inside a hash map.

Multiple different action sequences may produce the same vector, so frequencies must be accumulated.

Step 5: Enumerate All Right-Half States

Perform the same DFS on the right half.

Suppose the current right-half sum is:

$$R$$

To reach the target:

$$L + R = Target$$

Therefore:

$$L = Target - R$$

Look up this required vector in the left-half frequency map.

Add its frequency to the answer.

Step 6: Return the Total Count

After all right-half states have been processed, the accumulated count is the answer.

Why it works

Every action sequence uniquely determines:

  • a left-half state
  • a right-half state

The combined exponent vector equals the sum of the two half vectors.

The algorithm counts exactly those pairs whose sum equals the target exponent vector. Since every sequence appears in exactly one pair and every valid pair corresponds to a valid sequence, the count is correct.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countSequences(self, nums: List[int], k: int) -> int:
        target = [0, 0, 0]

        for idx, p in enumerate((2, 3, 5)):
            while k % p == 0:
                target[idx] += 1
                k //= p

        if k != 1:
            return 0

        vectors = []
        for x in nums:
            e2 = e3 = e5 = 0

            y = x
            while y % 2 == 0:
                e2 += 1
                y //= 2

            while y % 3 == 0:
                e3 += 1
                y //= 3

            while y % 5 == 0:
                e5 += 1
                y //= 5

            vectors.append((e2, e3, e5))

        n = len(vectors)
        mid = n // 2

        left = vectors[:mid]
        right = vectors[mid:]

        left_count = defaultdict(int)

        def dfs_left(i: int, a: int, b: int, c: int) -> None:
            if i == len(left):
                left_count[(a, b, c)] += 1
                return

            x, y, z = left[i]

            dfs_left(i + 1, a + x, b + y, c + z)
            dfs_left(i + 1, a - x, b - y, c - z)
            dfs_left(i + 1, a, b, c)

        dfs_left(0, 0, 0, 0)

        answer = 0

        def dfs_right(i: int, a: int, b: int, c: int) -> None:
            nonlocal answer

            if i == len(right):
                need = (
                    target[0] - a,
                    target[1] - b,
                    target[2] - c,
                )
                answer += left_count.get(need, 0)
                return

            x, y, z = right[i]

            dfs_right(i + 1, a + x, b + y, c + z)
            dfs_right(i + 1, a - x, b - y, c - z)
            dfs_right(i + 1, a, b, c)

        dfs_right(0, 0, 0, 0)

        return answer

Implementation Explanation

The first section factorizes k into exponents of 2, 3, and 5. If another prime remains, the function immediately returns zero because no sequence of operations can create that prime factor.

Next, every number in nums is converted into a three-dimensional exponent vector. This removes the need to work with rational numbers directly.

The array is split into two halves. The left DFS generates all possible exponent sums and stores their frequencies in a hash map.

The right DFS generates all possible exponent sums for the second half. For each sum, it computes the complementary vector required from the left half and adds the matching frequency.

The final accumulated count is returned.

Go Solution

package main

func countSequences(nums []int, k int64) int {
	target := [3]int{}

	primes := []int64{2, 3, 5}

	for i, p := range primes {
		for k%p == 0 {
			target[i]++
			k /= p
		}
	}

	if k != 1 {
		return 0
	}

	type Vec struct {
		a int
		b int
		c int
	}

	vectors := make([]Vec, len(nums))

	for i, x := range nums {
		e2, e3, e5 := 0, 0, 0

		for x%2 == 0 {
			e2++
			x /= 2
		}

		for x%3 == 0 {
			e3++
			x /= 3
		}

		for x%5 == 0 {
			e5++
			x /= 5
		}

		vectors[i] = Vec{e2, e3, e5}
	}

	n := len(vectors)
	mid := n / 2

	left := vectors[:mid]
	right := vectors[mid:]

	leftCount := make(map[Vec]int)

	var dfsLeft func(int, int, int, int)

	dfsLeft = func(i, a, b, c int) {
		if i == len(left) {
			leftCount[Vec{a, b, c}]++
			return
		}

		v := left[i]

		dfsLeft(i+1, a+v.a, b+v.b, c+v.c)
		dfsLeft(i+1, a-v.a, b-v.b, c-v.c)
		dfsLeft(i+1, a, b, c)
	}

	dfsLeft(0, 0, 0, 0)

	answer := 0

	var dfsRight func(int, int, int, int)

	dfsRight = func(i, a, b, c int) {
		if i == len(right) {
			need := Vec{
				target[0] - a,
				target[1] - b,
				target[2] - c,
			}

			answer += leftCount[need]
			return
		}

		v := right[i]

		dfsRight(i+1, a+v.a, b+v.b, c+v.c)
		dfsRight(i+1, a-v.a, b-v.b, c-v.c)
		dfsRight(i+1, a, b, c)
	}

	dfsRight(0, 0, 0, 0)

	return answer
}

Go-Specific Notes

The Go implementation mirrors the Python solution closely.

A small Vec struct is used as the hash map key because Go maps require comparable key types. Since the exponent vector contains only three integers, a struct is an efficient representation.

The answer comfortably fits inside Go's int because the total number of sequences is at most:

$$3^{19} = 1,162,261,467$$

which is below the limit of a 32-bit signed integer.

Worked Examples

Example 1

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

Target factorization:

6 = 2^1 * 3^1

Target vector:

(1,1,0)

Number vectors:

Number Vector
2 (1,0,0)
3 (0,1,0)
2 (1,0,0)

Valid sums reaching (1,1,0):

Choice Sequence Sum
M, M, N (1,1,0)
N, M, M (1,1,0)

Answer:

2

Example 2

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

Target vector:

(1,0,0)

Vectors:

Number Vector
4 (2,0,0)
6 (1,1,0)
3 (0,1,0)

Two assignments produce the target vector:

Sequence Resulting Vector
+4, -6, +3 (1,0,0)
0, +6, -3 (1,0,0)

Answer:

2

Example 3

nums = [1,5]
k = 1

Target vector:

(0,0,0)

Vectors:

Number Vector
1 (0,0,0)
5 (0,0,1)

For the first element:

  • multiply
  • divide
  • ignore

all produce the same exponent contribution (0,0,0).

For the second element, only "ignore" keeps exponent (0,0,0).

Total:

3

Complexity Analysis

Measure Complexity Explanation
Time O(3^(n/2)) Enumerate all states of both halves
Space O(3^(n/2)) Store left-half frequency map

With n ≤ 19, the largest half contains at most 10 elements. Therefore the number of states is at most:

$$3^{10} = 59049$$

which is easily manageable.

Test Cases

s = Solution()

assert s.countSequences([2, 3, 2], 6) == 2      # example 1
assert s.countSequences([4, 6, 3], 2) == 2      # example 2
assert s.countSequences([1, 5], 1) == 3         # example 3

assert s.countSequences([2], 2) == 1            # single multiply
assert s.countSequences([2], 1) == 1            # single ignore
assert s.countSequences([2], 4) == 0            # impossible target

assert s.countSequences([1], 1) == 3            # multiply/divide/ignore all valid

assert s.countSequences([5], 5) == 1            # single prime factor
assert s.countSequences([5], 25) == 0           # insufficient exponent

assert s.countSequences([2, 2], 1) == 3         # (+,-), (-,+), (0,0)

assert s.countSequences([6, 6], 36) == 1        # multiply both

assert s.countSequences([2, 3], 7) == 0         # prime factor > 5

assert s.countSequences([4, 4, 4], 16) > 0      # repeated exponents

assert s.countSequences([1] * 19, 1) == 3 ** 19 # maximum branching

Test Summary

Test Why
[2,3,2], 6 Official example 1
[4,6,3], 2 Official example 2
[1,5], 1 Official example 3
[2], 2 Single multiplication
[2], 1 Ignore operation
[2], 4 Impossible target
[1], 1 All three actions equivalent
[5], 5 Single prime factor
[5], 25 Missing exponent
[2,2], 1 Cancellation behavior
[6,6], 36 Multiple multiplications
[2,3], 7 Unsupported prime factor
[4,4,4], 16 Repeated exponent vectors
[1]*19, 1 Maximum number of valid sequences

Edge Cases

Target Contains a Prime Factor Larger Than 5

A common mistake is attempting to represent arbitrary values of k. Since every number in nums is at most 6, operations can only change exponents of 2, 3, and 5. If factorization of k leaves a remainder greater than 1, the answer must be zero. The implementation checks this immediately after factorization.

Numbers Equal to 1

The value 1 contributes exponent vector (0,0,0). Multiplying by 1, dividing by 1, and ignoring it are three distinct choices even though they produce the same value. A solution that deduplicates states incorrectly would undercount. The frequency map stores counts of sequences, not merely reachable vectors, so all three choices are counted correctly.

Target Equal to 1

When k = 1, the target vector becomes (0,0,0). Many different combinations of multiplications and divisions can cancel each other out. The meet-in-the-middle approach naturally counts all exponent sums that cancel to zero, ensuring every valid sequence is included.

Large Arrays of Ones

For nums = [1,1,...,1], every choice sequence keeps the value equal to 1. The correct answer becomes 3^n. The algorithm handles this efficiently because identical exponent vectors are aggregated into frequency counts rather than processed individually during matching.