Leetcode 2338. Count the Number of Ideal Arrays

Jimmy   Apr 22, 2025   1760 words   ~45 mins
#Math #Dynamic Programming #Combinatorics #Number Theory

Table of Contents

Problem Informations

Problem Description

You are given two integers n and maxValue, which are used to describe an ideal array.

A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:

  • Every arr[i] is a value from 1 to maxValue, for $0 \leq i < n$.
  • Every arr[i] is divisible by arr[i - 1], for $0 < i < n$.

Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo $10^9 + 7$.

Example 1:

  • Input: n = 2, maxValue = 5

  • Output: 10

  • Explanation: The following are the possible ideal arrays:

    • Arrays starting with the value 1 (5 arrays): [1,1], [1,2], [1,3], [1,4], [1,5]
    • Arrays starting with the value 2 (2 arrays): [2,2], [2,4]
    • Arrays starting with the value 3 (1 array): [3,3]
    • Arrays starting with the value 4 (1 array): [4,4]
    • Arrays starting with the value 5 (1 array): [5,5]

    There are a total of 5 + 2 + 1 + 1 + 1 = 10 distinct ideal arrays.

Example 2:

  • Input: n = 5, maxValue = 3

  • Output: 11

  • Explanation: The following are the possible ideal arrays:

    • Arrays starting with the value 1 (9 arrays):
      • With no other distinct values (1 array): [1,1,1,1,1]
      • With 2nd distinct value 2 (4 arrays): [1,1,1,1,2], [1,1,1,2,2], [1,1,2,2,2], [1,2,2,2,2]
      • With 2nd distinct value 3 (4 arrays): [1,1,1,1,3], [1,1,1,3,3], [1,1,3,3,3], [1,3,3,3,3]
    • Arrays starting with the value 2 (1 array): [2,2,2,2,2]
    • Arrays starting with the value 3 (1 array): [3,3,3,3,3]

    There are a total of 9 + 1 + 1 = 11 distinct ideal arrays.

Constraints:

  • $2 \leq n \leq 10^4$
  • $1 \leq maxValue \leq 10^4$

Intuition

The problem requires finding the number of distinct ideal arrays of a specified length n, where each element is a divisor of its preceding element and each element is bounded by a maximum value maxValue. This problem can be approached via combinatorial mathematics, specifically focusing on the divisor properties and prime factorization, since each arr[i] must be divisible by arr[i-1]. The challenge involves efficiently counting valid permutations of these conditions, especially given the constraints on n and maxValue.

Approach

To solve the problem, an algorithm is designed to leverage combinatorial mathematics through factorial computations and prime factorization. The approach follows these primary steps:

  1. Precompute Factorials and Inverses:

    • Compute factorials and their modular inverses up to a maximum limit (maxN) using Fermat’s Little Theorem which enables modular arithmetic for division. This is essential for efficiently calculating combinatorial combinations later.
    • The approach uses modular exponentiation to handle large numbers and prevent integer overflow, specifically by precomputing factorials and their inverses modulo $10^9 + 7$.

  2. Iterate Over Potential Starting Values:

    • For each starting integer i from 1 to maxValue, evaluate its role as the initial value of the ideal array. This starting integer determines the potential divisors for subsequent values in the array.

  3. Prime Factorization:

    • Perform prime factorization on the starting integer i. By expressing i in terms of its prime factors, we can find combinations of array elements whose product or repetition fits the divisor requirement.

  4. Combinations and Repeated Combinations Calculation:

    • For each prime factor, compute the number of combinatorial arrangements using the formula for combinations with repetition: $H(n, k) = C(n + k - 1, k)$ where $C$ denotes binomial coefficients. This formula represents distributing n indistinguishable items into k distinguishable bins.
    • Accumulate the combinations for each prime factor to calculate the total combinations possible for that starting integer.

  5. Aggregate Results:

    • Sum up all outcomes over all possible starting values modulo $10^9 + 7$ to achieve the final count of distinct ideal arrays.

By utilizing factorials, inverse factorials, and combinatorial mathematics, this approach efficiently computes the desired count despite potentially large input values restrained by the given constraints. The implementation ensures all calculations adhere to modular arithmetic due to the constraint on returning results modulo $10^9 + 7$.

Code

C++

class Solution {
private:
    const long long MOD = 1e9 + 7;
    std::vector<long long> fact, invFact;

    // Function to perform prime factorization of a given number n
    vector<pair<long long, long long>> primeFactorization(long long n) {
        vector<pair<long long, long long>> factors;
        
        // Factor out 2 from n
        long long count = 0;
        while (n % 2 == 0) {
            count++;
            n /= 2;
        }
        if (count > 0) {
            factors.push_back({2, count});
        }
        
        // Factor out all odd numbers from n
        for (long long i = 3; i <= sqrt(n); i += 2) {
            count = 0;
            while (n % i == 0) {
                count++;
                n /= i;
            }
            if (count > 0) {
                factors.push_back({i, count});
            }
        }
        
        // If remaining n is greater than 2 then it is prime
        if (n > 2) {
            factors.push_back({n, 1});
        }

        return factors;
    }
    
    // Function to compute a^b % mod using iterative exponentiation
    long long modPow(long long a, long long b, long long mod) {
        long long res = 1;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            b /= 2;
        }
        return res;
    }
    
    // Precompute factorials and their modular inverses up to maxN
    void precompute(int maxN, long long mod) {
        fact.resize(maxN + 1);
        invFact.resize(maxN + 1);
        fact[0] = 1;
        for (int i = 1; i <= maxN; ++i) {
            fact[i] = fact[i - 1] * i % mod;
        }
        invFact[maxN] = modPow(fact[maxN], mod - 2, mod);  // Using Fermat's Little Theorem for the inverse
        for (int i = maxN - 1; i >= 0; --i) {
            invFact[i] = invFact[i + 1] * (i + 1) % mod;
        }
    }
    
    // Function to compute C(n, k) % mod
    long long comb(long long n, long long k, long long mod) {
        if (k > n || k < 0) return 0;
        return fact[n] * invFact[k] % mod * invFact[n - k] % mod;
    }
    
    // Function to compute H(n, k) = C(n + k - 1, k) % mod
    long long repeatedComb(long long n, long long k, long long mod) {
        return comb(n + k - 1, k, mod);
    }
    
public:
    int idealArrays(int n, int maxValue) {
        long long ans = 0;
        int maxN = 10012;  // Maximum range for precomputation
        precompute(maxN, MOD);  // Precomputing factorials and inverses

        // Iterate over all possible starting integers from 1 to maxValue
        for (int i = 1; i <= maxValue; i++) {
            vector<pair<long long, long long>> primes = primeFactorization(i);
            long long cur_ans = 1;
            
            // Calculate product of combinations for each prime factor of i
            for (pair<long long, long long>& prime : primes) {
                cur_ans = cur_ans * repeatedComb(n, prime.second, MOD) % MOD;
            }
            
            // Add the result for this starting integer to the final answer
            ans += cur_ans;
            ans %= MOD;
        }

        return ans;
    }
};

Python

class Solution:
    def __init__(self):
        self.MOD = int(1e9 + 7)
        self.fact = []
        self.invFact = []

    # Function to perform prime factorization of a given number n
    def primeFactorization(self, n):
        factors = []
        
        # Factor out 2 from n
        count = 0
        while n % 2 == 0:
            count += 1
            n //= 2
        if count > 0:
            factors.append((2, count))
        
        # Factor out all odd numbers from n
        i = 3
        while i <= int(n**0.5):
            count = 0
            while n % i == 0:
                count += 1
                n //= i
            if count > 0:
                factors.append((i, count))
            i += 2
        
        # If remaining n is greater than 2 then it is prime
        if n > 2:
            factors.append((n, 1))

        return factors
    
    # Function to compute a^b % mod using iterative exponentiation
    def modPow(self, a, b, mod):
        res = 1
        while b > 0:
            if b % 2 == 1:
                res = (res * a) % mod
            a = (a * a) % mod
            b //= 2
        return res
    
    # Precompute factorials and their modular inverses up to maxN
    def precompute(self, maxN, mod):
        self.fact = [0] * (maxN + 1)
        self.invFact = [0] * (maxN + 1)
        self.fact[0] = 1
        for i in range(1, maxN + 1):
            self.fact[i] = self.fact[i - 1] * i % mod
        self.invFact[maxN] = self.modPow(self.fact[maxN], mod - 2, mod)  # Using Fermat's Little Theorem for the inverse
        for i in range(maxN - 1, -1, -1):
            self.invFact[i] = self.invFact[i + 1] * (i + 1) % mod
    
    # Function to compute C(n, k) % mod
    def comb(self, n, k, mod):
        if k > n or k < 0:
            return 0
        return self.fact[n] * self.invFact[k] % mod * self.invFact[n - k] % mod
    
    # Function to compute H(n, k) = C(n + k - 1, k) % mod
    def repeatedComb(self, n, k, mod):
        return self.comb(n + k - 1, k, mod)
    
    def idealArrays(self, n, maxValue):
        ans = 0
        maxN = 10012  # Maximum range for precomputation
        self.precompute(maxN, self.MOD)  # Precomputing factorials and inverses

        # Iterate over all possible starting integers from 1 to maxValue
        for i in range(1, maxValue + 1):
            primes = self.primeFactorization(i)
            cur_ans = 1
            
            # Calculate product of combinations for each prime factor of i
            for prime in primes:
                cur_ans = cur_ans * self.repeatedComb(n, prime[1], self.MOD) % self.MOD
            
            # Add the result for this starting integer to the final answer
            ans += cur_ans
            ans %= self.MOD

        return ans

Complexity

  • Time complexity: $O(\sqrt{maxValue} \cdot \log(maxValue) + maxValue \cdot \log(n) + n)$

    Explanation:

    • The idealArrays function iterates over every integer from 1 to maxValue, resulting in $O(maxValue)$ iterations.
    • For each integer i, the primeFactorization function is called.
      • The time complexity for primeFactorization is $O(\sqrt{i})$. In the worst case, this is $O(\sqrt{maxValue})$ when factoring maxValue.
    • The repeatedComb function calls the comb function, which computes binomial coefficients using precomputed factorial values.
      • The precomputation of factorials in precompute is $O(maxN)$, which corresponds to $O(n)$. The computation of the binomial coefficient itself is $O(\log(n))$ due to the number of modular multiplications required.
    • Therefore, the combined time complexity is $O(\sqrt{maxValue} \cdot maxValue + maxValue \cdot \log(n) + n)$. Simplifying assumptions about the density of numbers with respect to their prime factors lead to $O(\sqrt{maxValue} \cdot \log(maxValue) + maxValue \cdot \log(n) + n)$.

  • Space complexity: $O(n)$

    Explanation:

    • The space complexity is primarily determined by the storage of factorial and inverse factorial arrays(fact and invFact) in the precompute function.
    • These arrays are sized up to maxN, corresponding to $O(n)$ since maxN is set to accommodate the problem constraints that $n \leq 10000$.
    • The space used for storing prime factors in the primeFactorization function is negligible compared to the factorial arrays and is restricted to $O(\log(maxValue))$ space, which is dominated by the $O(n)$ factor.

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.