Count Ways to Make Array With Product

Problem Id: 1735 Difficulty: Hard Tag: Math


Intuition

  1. Generate primes less than 10,000.
  2. For each query, a. Decompose prime factors. b. Put the same primes into slots.

Solution


from typing import List
import math


class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        primes = self._get_primes(10000)
        factorials = [1]
        for i in range(1, 10001):
            factorials.append((factorials[-1] * i) % 1000000007)

        result = []
        for slots, num in queries:
            ways = 1
            if slots > 1:
                prime_factor_counts = self._prime_factor_counts(primes, num)
                ways = 1
                for counts in prime_factor_counts:
                    ways *= self._big_c(factorials, slots + num - 1, slots - 1)
            result.append(ways % 1000000007)
        return result

    def _get_primes(self, m):
        primes = set()
        for i in range(2, m + 1):
            is_prime = True
            for p in primes:
                if i % p == 0:
                    is_prime = False
                    break
            if is_prime:
                primes.add(i)
        return primes

    def _big_c(self, factorials, n, k):
        return factorials[n] / factorials[k] / factorials[n - k]

    def _prime_factor_counts(self, primes, num):
        factors_count = {}
        for p in primes:
            if num % 2 == 0:
                factors_count[p] = 0
            while num % 2 == 0:
                factors_count[p] += 1
                num = num // p
            if num == 1:
                break
        return factors_count.values()