Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Count the Number of Ideal Arrays solution and explanation

HardCombinatoricsDynamic ProgrammingMathNumber Theory8 min read57.0% acceptanceUpdated 9 Apr 2026
Asked atInfosysGoogleAmazonMicrosoft
Practise Count the Number of Ideal Arrays
1:15:46
Count the Number of Ideal Arrays | Detailed Explanation | Explained Maths | Leetcode 2338 | MIKcodestorywithMIK · 1:15:46 · 8K viewsWatch on YouTube
9 more videos on this problem
  1. Count the Number of Ideal Arrays | Detailed Explanation | Explained Maths | Leetcode 2338 | MIKcodestorywithMIK · 1:15:46 · 8K views
  2. Count the Number of Ideal Arrays | Leetcode 2338Techdose · 43:18 · 7K views
  3. Weekly Contest 301 | 2338. Count the Number of Ideal ArrayscodingMohan · 33:00 · 6K views
  4. Leetcode 2338. Count the Number of Ideal Arrays | HindiThinkCode · 23:57 · 3K views
  5. 2338. Count the Number of Ideal Arrays | Leetcode Daily - PythonLeetcode Daily · 12:34 · 2K views
  6. 【每日一题】LeetCode 2338. Count the Number of Ideal ArraysHuifeng Guan · 35:22 · 1K views
  7. Daily Leetcode #1848: Apr 22, 2025 - 2338. Count the Number of Ideal ArraysProgramming Live with Larry · 36:57 · 1K views
  8. LeetCode 2338. Count the Number of Ideal Arrays | Full Explanation | DP + Combinatorics 🔥Code Harmony · 42:13 · 1K views
  9. 2338. Count the Number of Ideal Arrays (Leetcode Hard)Programming Live with Larry · 2:43:54 · 1K views
  10. Leetcode 2338. Count the Number of Ideal Arrays | Math + Combinations + DP on Factors ExplainedStatLearn Tech · 18:08 · 932 views

The 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 109 + 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 <= n <= 104
  • 1 <= maxValue <= 104

Approach overview

Problem Overview: Count how many arrays of length n you can build where every element is between 1 and maxValue, and each element divides the next (a[i] | a[i+1]). The divisibility constraint forms multiplicative chains, which means each valid array corresponds to repeatedly multiplying by factors.

Approach 1: Dynamic Programming on Multiples (Time: O(maxValue * log(maxValue) * L), Space: O(maxValue * L))

This method builds arrays by extending smaller valid sequences. Define dp[len][v] as the number of arrays of length len ending with value v. For each value v, iterate through its multiples (2v, 3v, ...) and update the next length. The divisibility rule holds automatically because every multiple of v is divisible by v. The maximum chain length L is small (about 14 when maxValue ≤ 10^4) because values grow multiplicatively. This keeps the DP manageable and avoids exploring impossible long chains.

Precomputing multiples lets transitions run quickly. Each step distributes counts from smaller numbers to their multiples. The final result sums the number of valid chains of all lengths and distributes them across the n positions using combinations. This approach highlights the structure of divisibility chains and fits naturally with dynamic programming.

Approach 2: Combinatorics with Sieve of Eratosthenes (Time: O(maxValue log maxValue), Space: O(maxValue))

The key insight: every ideal array corresponds to choosing a final value and distributing its prime factors across n positions. Factorize each value ≤ maxValue. If a value has prime factorization p1^e1 * p2^e2 * ..., each exponent represents how many multiplicative steps must appear across the array. The number of ways to distribute e identical increases across n positions equals C(n - 1 + e, e) (stars and bars).

Use the Sieve of Eratosthenes to precompute smallest prime factors and factorize every number quickly. For each exponent in the factorization, multiply the combinations. Sum the results for all values from 1 to maxValue. Precompute combinations with Pascal's triangle or factorial + modular inverse under modulo 1e9+7. This converts the divisibility chain problem into a pure combinatorics calculation.

Recommended for interviews: The combinatorial approach with prime factorization is the expected optimal solution. It reduces the problem to counting exponent distributions and runs in roughly O(maxValue log maxValue). Implementing the DP approach first shows understanding of the divisibility structure, but the combinatorial method demonstrates stronger algorithmic insight and is usually what interviewers look for in hard math problems.

Approach 1: Dynamic Programming

The key idea is to use dynamic programming to count the number of ways to fill each position in the array. We use a DP table where dp[i][j] represents the number of ways to fill up to the i-th position in the array ending with value j. We initialize the first position and iteratively compute the subsequent positions considering the divisibility constraint.

MOD = 1000000007

class Solution:
    def countIdealArrays(self, n: int, maxValue: int) -> int:
        dp = [[0] * (maxValue + 1) for _ in range(n + 1)]
        for i in range(1, maxValue + 1):
            dp[1][i] = 1

        for i in range(2, n + 1):
            for j in range(1, maxValue + 1):
                k = j
                while k <= maxValue:
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD
                    k += j

        result = 0
        for i in range(1, maxValue + 1):
            result = (result + dp[n][i]) % MOD
        return result

if __name__ == "__main__":
    solution = Solution()
    print(solution.countIdealArrays(2, 5))
import java.util.*;

public class IdealArrays {
    static final int MOD = 1000000007;
    public static int countIdealArrays(int n, int maxValue) {
        long[][] dp = new long[n + 1][maxValue + 1];
        for (int i = 1; i <= maxValue; i++)
            dp[1][i] = 1L;

        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= maxValue; j++) {
                for (int k = j; k <= maxValue; k += j) {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
                }
            }
        }

        long result = 0;
        for (int i = 1; i <= maxValue; i++) {
            result = (result + dp[n][i]) % MOD;
        }
        return (int)result;
    }

    public static void main(String[] args) {
        int n = 2, maxValue = 5;
        System.out.println(countIdealArrays(n, maxValue));
    }
}
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;

int countIdealArrays(int n, int maxValue) {
    vector<vector<long long>> dp(n + 1, vector<long long>(maxValue + 1, 0));
    for (int i = 1; i <= maxValue; i++)
        dp[1][i] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= maxValue; j++) {
            for (int k = j; k <= maxValue; k += j) {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
            }
        }
    }

    long long result = 0;
    for (int i = 1; i <= maxValue; i++) {
        result = (result + dp[n][i]) % MOD;
    }
    return result;
}

int main() {
    int n = 2, maxValue = 5;
    cout << countIdealArrays(n, maxValue) << endl;
    return 0;
}
const MOD = 1000000007;

function countIdealArrays(n, maxValue) {
    let dp = Array.from({ length: n + 1 }, () => new Array(maxValue + 1).fill(0));
    for (let i = 1; i <= maxValue; i++)
        dp[1][i] = 1;
    
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= maxValue; j++) {
            for (let k = j; k <= maxValue; k += j) {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
            }
        }
    }

    let result = 0;
    for (let i = 1; i <= maxValue; i++) {
        result = (result + dp[n][i]) % MOD;
    }
    return result;
}

console.log(countIdealArrays(2, 5));
#include <stdio.h>
#define MOD 1000000007

int countIdealArrays(int n, int maxValue) {
    long long dp[n+1][maxValue+1];
    for (int i = 1; i <= maxValue; i++) 
        dp[1][i] = 1;
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= maxValue; j++) {
            dp[i][j] = 0;
            for (int k = j; k <= maxValue; k += j) {
                dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
            }
        }
    }
    
    long long result = 0;
    for (int i = 1; i <= maxValue; i++) {
        result = (result + dp[n][i]) % MOD;
    }
    return (int)result;
}

int main() {
    int n = 2, maxValue = 5;
    printf("%d\n", countIdealArrays(n, maxValue));
    return 0;
}
using System;

class IdealArrays {
    const int MOD = 1000000007;
    public static int CountIdealArrays(int n, int maxValue) {
        long[,] dp = new long[n + 1, maxValue + 1];
        for (int i = 1; i <= maxValue; i++)
            dp[1, i] = 1L;
        
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= maxValue; j++) {
                for (int k = j; k <= maxValue; k += j) {
                    dp[i, j] = (dp[i, j] + dp[i-1, k]) % MOD;
                }
            }
        }

        long result = 0;
        for (int i = 1; i <= maxValue; i++) {
            result = (result + dp[n, i]) % MOD;
        }
        return (int)result;
    }

    public static void Main(string[] args) {
        Console.WriteLine(CountIdealArrays(2, 5));
    }
}

This Python solution initializes a DP table with zeros. It sets up an initial array state and iteratively fills each position based on the divisibility condition, storing valid combinations in the DP table.

Complexity

Time complexity is O(n * maxValue^2). Space complexity is O(n * maxValue).

Try this approach in the editor

Approach 2: Combinatorial with Sieve of Eratosthenes

In this approach, we employ a mathematical strategy using combinatorics and the Sieve of Eratosthenes algorithm. By precomputing factors and valid sequences, we reduce the number of operations needed to determine valid ideal arrays.

MOD = 1000000007

def countIdealArrays(n: int, maxValue: int) -> int:
    dp = [1] * (maxValue + 1)

    for k in range(2, n + 1):
        for i in range(maxValue, 0, -1):
            sum_ = 0
            for j in range(2 * i, maxValue + 1, i):
                sum_ = (sum_ + dp[j]) % MOD
            dp[i] = (dp[i] + sum_) % MOD

    res = sum(dp[i] for i in range(1, maxValue + 1)) % MOD
    return res

if __name__ == '__main__':
    print(countIdealArrays(2, 5))
import java.util.*;

public class IdealArrays {
    static final int MOD = 1000000007;

    private static long comb(int n, int k) {
        if (k > n) return 0;
        if (k > n - k) k = n - k;
        long c = 1;
        for (int i = 0; i < k; ++i) {
            c = c * (n - i) / (i + 1);
        }
        return c % MOD;
    }

    public static int countIdealArrays(int n, int maxValue) {
        long[] dp = new long[maxValue + 1];
        Arrays.fill(dp, 1L);

        for (int k = 2; k <= n; ++k) {
            for (int i = maxValue; i >= 1; --i) {
                long sum = 0;
                for (int j = 2 * i; j <= maxValue; j += i) {
                    sum = (sum + dp[j]) % MOD;
                }
                dp[i] = (dp[i] + sum) % MOD;
            }
        }

        long res = 0;
        for (int i = 1; i <= maxValue; ++i) {
            res = (res + dp[i]) % MOD;
        }
        return (int) res;
    }

    public static void main(String[] args) {
        System.out.println(countIdealArrays(2, 5));
    }
}
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;

int comb(int n, int k) {
    if (k > n) return 0;
    if (k > n - k) k = n - k;
    long long c = 1;
    for (int i = 0; i < k; ++i) {
        c = c * (n - i) / (i + 1);
    }
    return c % MOD;
}

int countIdealArrays(int n, int maxValue) {
    vector<long long> dp(maxValue + 1, 1);

    for (int k = 2; k <= n; ++k) {
        for (int i = maxValue; i >= 1; --i) {
            long long sum = 0;
            for (int j = 2 * i; j <= maxValue; j += i) {
                sum = (sum + dp[j]) % MOD;
            }
            dp[i] = (dp[i] + sum) % MOD;
        }
    }

    long long res = 0;
    for (int i = 1; i <= maxValue; ++i) {
        res = (res + dp[i]) % MOD;
    }
    return res;
}

int main() {
    int n = 2, maxValue = 5;
    cout << countIdealArrays(n, maxValue) << endl;
    return 0;
}
const MOD = 1000000007;

function countIdealArrays(n, maxValue) {
    let dp = new Array(maxValue + 1).fill(1);

    for (let k = 2; k <= n; ++k) {
        for (let i = maxValue; i >= 1; --i) {
            let sum = 0;
            for (let j = 2 * i; j <= maxValue; j += i) {
                sum = (sum + dp[j]) % MOD;
            }
            dp[i] = (dp[i] + sum) % MOD;
        }
    }

    let res = 0;
    for (let i = 1; i <= maxValue; ++i) {
        res = (res + dp[i]) % MOD;
    }
    return res;
}

console.log(countIdealArrays(2, 5));
#include <stdio.h>
#define MOD 1000000007

// Function to compute combinations
long long comb(int n, int k) {
    if (k > n) return 0;
    if (k > n - k) k = n - k;
    long long c = 1;
    for (int i = 0; i < k; ++i) {
        c = c * (n - i) / (i + 1);
    }
    return c % MOD;
}

int countIdealArrays(int n, int maxValue) {
    long long dp[maxValue + 1];
    for (int i = 1; i <= maxValue; ++i) dp[i] = 1;

    for (int k = 2; k <= n; ++k) {
        for (int i = maxValue; i >= 1; --i) {
            long long sum = 0;
            for (int j = 2 * i; j <= maxValue; j += i) {
                sum = (sum + dp[j]) % MOD;
            }
            dp[i] = (dp[i] + sum) % MOD;
        }
    }

    long long res = 0;
    for (int i = 1; i <= maxValue; ++i) {
        res = (res + dp[i]) % MOD;
    }
    return res;
}

int main() {
    int n = 2, maxValue = 5;
    printf("%d\n", countIdealArrays(n, maxValue));
    return 0;
}
using System;

class IdealArrays {
    const int MOD = 1000000007;
    
    public static int CountIdealArrays(int n, int maxValue) {
        long[] dp = new long[maxValue + 1];
        for (int i = 1; i <= maxValue; ++i)
            dp[i] = 1;

        for (int k = 2; k <= n; ++k) {
            for (int i = maxValue; i >= 1; --i) {
                long sum = 0;
                for (int j = 2 * i; j <= maxValue; j += i) {
                    sum = (sum + dp[j]) % MOD;
                }
                dp[i] = (dp[i] + sum) % MOD;
            }
        }

        long res = 0;
        for (int i = 1; i <= maxValue; ++i) {
            res = (res + dp[i]) % MOD;
        }
        return (int)res;
    }

    public static void Main() {
        Console.WriteLine(CountIdealArrays(2, 5));
    }
}

This Python variant leverages an iterative update across potential factors, iteratively summing possible sequences and reapplying results across necessary indices in a sieve-like manner.

Complexity

The time complexity is handled efficiently within O(n * maxValue * log(maxValue)), mitigating overuse of combinatorial expansion.

Try this approach in the editor

Approach 3: Dynamic Programming

Let f[i][j] represent the number of sequences ending with i and consisting of j distinct elements. The initial value is f[i][1] = 1.

Consider n balls, which are eventually divided into j parts. Using the "separator method," we can insert j-1 separators into the n-1 positions, and the number of combinations is c_{n-1}^{j-1}.

We can preprocess the combination numbers c[i][j] using the recurrence relation c[i][j] = c[i-1][j] + c[i-1][j-1]. Specifically, when j=0, c[i][j] = 1.

The final answer is:

$ sum\limits_{i=1}^{k}sum\limits_{j=1}^{log_2 k + 1} f[i][j] times c_{n-1}^{j-1}

where k represents the maximum value of the array, i.e., maxValue.

  • Time Complexity: O(m times log^2 m)
  • Space Complexity: O(m times log m)$
func idealArrays(n int, maxValue int) int {
	mod := int(1e9) + 7
	m := maxValue
	c := make([][]int, n)
	f := make([][]int, m+1)
	for i := range c {
		c[i] = make([]int, 16)
	}
	for i := range f {
		f[i] = make([]int, 16)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	var dfs func(int, int) int
	dfs = func(i, cnt int) int {
		if f[i][cnt] != -1 {
			return f[i][cnt]
		}
		res := c[n-1][cnt-1]
		if cnt < n {
			for k := 2; k*i <= m; k++ {
				res = (res + dfs(k*i, cnt+1)) % mod
			}
		}
		f[i][cnt] = res
		return res
	}
	for i := 0; i < n; i++ {
		for j := 0; j <= i && j < 16; j++ {
			if j == 0 {
				c[i][j] = 1
			} else {
				c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
			}
		}
	}
	ans := 0
	for i := 1; i <= m; i++ {
		ans = (ans + dfs(i, 1)) % mod
	}
	return ans
}
Try this approach in the editor

Approach 4: Default Approach

function idealArrays(n: number, maxValue: number): number {
    const mod = 1e9 + 7;

    const c: number[][] = Array.from({ length: n }, () => Array(16).fill(0));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j <= i && j < 16; j++) {
            if (j === 0) {
                c[i][j] = 1;
            } else {
                c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
            }
        }
    }

    const f: number[][] = Array.from({ length: maxValue + 1 }, () => Array(16).fill(0));
    for (let i = 1; i <= maxValue; i++) {
        f[i][1] = 1;
    }

    for (let j = 1; j < 15; j++) {
        for (let i = 1; i <= maxValue; i++) {
            for (let k = 2; k * i <= maxValue; k++) {
                f[k * i][j + 1] = (f[k * i][j + 1] + f[i][j]) % mod;
            }
        }
    }

    let ans = 0;
    for (let i = 1; i <= maxValue; i++) {
        for (let j = 1; j < 16; j++) {
            ans = (ans + f[i][j] * c[n - 1][j - 1]) % mod;
        }
    }

    return ans;
}
func idealArrays(n int, maxValue int) (ans int) {
	const mod = int(1e9 + 7)
	c := make([][]int, n)
	for i := 0; i < n; i++ {
		c[i] = make([]int, 16)
		for j := 0; j <= i && j < 16; j++ {
			if j == 0 {
				c[i][j] = 1
			} else {
				c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod
			}
		}
	}

	f := make([][16]int, maxValue+1)
	for i := 1; i <= maxValue; i++ {
		f[i][1] = 1
	}
	for j := 1; j < 15; j++ {
		for i := 1; i <= maxValue; i++ {
			for k := 2; k*i <= maxValue; k++ {
				f[k*i][j+1] = (f[k*i][j+1] + f[i][j]) % mod
			}
		}
	}

	for i := 1; i <= maxValue; i++ {
		for j := 1; j < 16; j++ {
			ans = (ans + f[i][j]*c[n-1][j-1]) % mod
		}
	}
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Dynamic Programming

Time complexity is O(n * maxValue^2). Space complexity is O(n * maxValue).

Combinatorial with Sieve of Eratosthenes

The time complexity is handled efficiently within O(n * maxValue * log(maxValue)), mitigating overuse of combinatorial expansion.

Dynamic Programming–
Default Approach–

Complexity analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming on MultiplesO(maxValue * log(maxValue) * L)O(maxValue * L)When exploring divisibility chains directly or deriving the combinatorial insight step by step
Combinatorics with Sieve of EratosthenesO(maxValue log maxValue)O(maxValue)Optimal solution for large constraints using prime factorization and combinations

Frequently asked questions

Is Count the Number of Ideal Arrays easy or hard?

LeetCode classifies this problem as Hard because it requires recognizing the connection between divisibility chains and prime factor distributions. The optimal solution combines number theory, combinatorics, and modular arithmetic.

Count the Number of Ideal Arrays Python/Java solution

Implementations typically precompute smallest prime factors and combination values modulo 1e9+7. The algorithm iterates from 1 to maxValue, factorizes each number, computes combinations for each exponent, and accumulates the result. The same logic works in Python, Java, C++, and other languages.

What is the best approach for Count the Number of Ideal Arrays?

The optimal approach uses combinatorics with prime factorization. Factorize each value up to maxValue using a sieve, then distribute prime exponents across n positions using combinations C(n-1+e, e). This reduces the problem to O(maxValue log maxValue) time and avoids building arrays explicitly.

Is Count the Number of Ideal Arrays asked at Google/Amazon/Meta?

Problems combining combinatorics, dynamic programming, and number theory appear frequently in interviews at companies like Google and Meta. Hard counting problems similar to this are commonly used to evaluate mathematical reasoning and optimization skills.

What data structure is used in Count the Number of Ideal Arrays?

The solution primarily relies on arrays for dynamic programming or for storing smallest prime factors from a sieve. Mathematical structures like combinations and factorial tables are also used for fast combinatorial calculations.

What is the time complexity of Count the Number of Ideal Arrays?

The optimal solution runs in O(maxValue log maxValue) time due to prime factorization using a sieve and constant-time combination calculations. Space complexity is O(maxValue) for storing smallest prime factors and precomputed combinations.

How to solve Count the Number of Ideal Arrays in O(maxValue log maxValue)?

Precompute smallest prime factors using the Sieve of Eratosthenes. For each value ≤ maxValue, factorize it and compute how many ways its prime exponents can be distributed across n positions using C(n-1+e, e). Multiply the results for each prime factor and sum across all values.

Comments

Next problem · similarCount Ways to Make Array With ProductHard
Now write it yourselfClose this page and solve Count the Number of Ideal Arrays in the editor, without looking.
Practise Count the Number of Ideal Arrays