Count the Number of Ideal Arrays - Practice Coding Problems

Count the Number of Ideal Arrays - Problem

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 <= 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 2, maxValue = 3

› Output: 5

💡 Note: The 5 ideal arrays are: [1,1], [1,2], [1,3], [2,2], [3,3]. Each array satisfies: all elements ≤ 3, and each element divides the next.

Example 2 — Longer Array

$ Input: n = 3, maxValue = 2

› Output: 4

💡 Note: The 4 ideal arrays are: [1,1,1], [1,1,2], [1,2,2], [2,2,2]. All arrays have length 3 with elements ≤ 2.

Example 3 — Single Element

$ Input: n = 1, maxValue = 4

› Output: 4

💡 Note: With length 1, any single value is ideal: [1], [2], [3], [4]. No divisibility constraint applies.

Constraints

2 ≤ n ≤ 10⁴
1 ≤ maxValue ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=2, maxValue=3

Generate

Find all arrays where each element divides the next

Count

Return total count: 5 ideal arrays

Key Takeaway

🎯 Key Insight: Ideal arrays follow divisibility chains, making this a combinatorial counting problem with prime factorization

Asked in

G Google 15 f Meta 8 a Amazon 5

This problem requires counting ideal arrays where each element divides the next. The key insight is that ideal arrays correspond to non-decreasing sequences of divisor relationships. The optimal approach uses prime factorization and combinatorics to count arrangements without generating them. Time: O(maxValue log log maxValue), Space: O(maxValue)

Common Approaches

Approach	Time	Space	Notes
✓ Combinatorics with Prime Factorization	O(maxValue log log maxValue + maxValue × π(maxValue) × n)	O(maxValue)	Use prime factorization and stars-and-bars combinatorics
Brute Force Recursion	O(maxValue^n)	O(n)	Generate all possible arrays and count valid ones
Dynamic Programming	O(n × maxValue²)	O(n × maxValue)	Use DP to count arrays ending with each value

Combinatorics with Prime Factorization — Algorithm Steps

Find all primes up to maxValue using sieve
For each starting value, compute prime factorization
Use stars-and-bars to count ways to distribute each prime power
Multiply counts for all primes to get total combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Factorize

Break down each number into prime factors

Distribute

Use stars-and-bars to count distributions

Multiply

Combine counts for all prime factors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

const int MOD = 1000000007;

long long pow_mod(long long base, long long exp, int mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

long long mod_inverse(long long a, int mod) {
    return pow_mod(a, mod - 2, mod);
}

long long combination(int n, int r, long long* fact) {
    if (r > n || r < 0) return 0;
    return (fact[n] * mod_inverse(fact[r], MOD) % MOD * mod_inverse(fact[n-r], MOD)) % MOD;
}

long long solution(int n, int maxValue) {
    // Precompute factorials
    long long* fact = (long long*)malloc((n + 20) * sizeof(long long));
    fact[0] = 1;
    for (int i = 1; i < n + 20; i++) {
        fact[i] = (fact[i-1] * i) % MOD;
    }
    
    // Find primes
    bool* isPrime = (bool*)malloc((maxValue + 1) * sizeof(bool));
    for (int i = 0; i <= maxValue; i++) isPrime[i] = true;
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; i * i <= maxValue; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= maxValue; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    int* primes = (int*)malloc(maxValue * sizeof(int));
    int primeCount = 0;
    for (int i = 2; i <= maxValue; i++) {
        if (isPrime[i]) {
            primes[primeCount++] = i;
        }
    }
    
    // Compute max powers
    int** maxPower = (int**)malloc((maxValue + 1) * sizeof(int*));
    for (int i = 0; i <= maxValue; i++) {
        maxPower[i] = (int*)calloc(primeCount, sizeof(int));
    }
    
    for (int num = 1; num <= maxValue; num++) {
        int temp = num;
        for (int pi = 0; pi < primeCount; pi++) {
            while (temp % primes[pi] == 0) {
                maxPower[num][pi]++;
                temp /= primes[pi];
            }
        }
    }
    
    long long result = 0;
    for (int start = 1; start <= maxValue; start++) {
        long long ways = 1;
        for (int pi = 0; pi < primeCount; pi++) {
            if (maxPower[start][pi] > 0) {
                ways = (ways * combination(maxPower[start][pi] + n - 1, n - 1, fact)) % MOD;
            }
        }
        result = (result + ways) % MOD;
    }
    
    // Free memory
    free(fact);
    free(isPrime);
    free(primes);
    for (int i = 0; i <= maxValue; i++) {
        free(maxPower[i]);
    }
    free(maxPower);
    
    return result;
}

int main() {
    int n, maxValue;
    scanf("%d", &n);
    scanf("%d", &maxValue);
    printf("%lld\n", solution(n, maxValue));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(maxValue log log maxValue + maxValue × π(maxValue) × n)

Sieve for primes plus factorization and combinatorics for each value

⚡ Linearithmic

Space Complexity

O(maxValue)

Space for sieve and prime factorizations

✓ Linear Space

25.0K Views

Medium Frequency

~45 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Combinatorics with Prime Factorization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler