Skip to main content
Talentd

Count the Number of Ideal Arrays - Solution & Explanation

HardMathDynamic ProgrammingCombinatoricsNumber Theory20 min readAsked at: Amazon, Microsoft, Infosys +1
Practice this problem

Problem Statement

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.

This solution uses a 2D array dp to compute the count of ideal arrays. The outer loop on i goes through the length of the desired array, while the inner nested loops iterate over possible values in the array, tracking which values are divisible by each other to construct valid sequences.

Code

CC++JavaPythonC#JavaScriptGo

C

C++

Java

Python

C#

JavaScript

Go

Complexity

The time complexity is O(n * maxValue^2) due to the nested loops. The space complexity is O(n * maxValue), as we store results for all positions and possible last values.

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.

This C implementation of the combinatorial approach calculates combinations efficiently, then uses a sieve-like update of valid ideal array counts. Each step leverages precomputed info for faster determination.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is approximately O(n * maxValue * log(maxValue)), relying on multiplication instead of iteration per number.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming

The time complexity is O(n * maxValue^2) due to the nested loops. The space complexity is O(n * maxValue), as we store results for all positions and possible last values.

Combinatorial with Sieve of Eratosthenes

Time complexity is approximately O(n * maxValue * log(maxValue)), relying on multiplication instead of iteration per number.

Default Approach—

Detailed 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

Video Solution

Count the Number of Ideal Arrays | Detailed Explanation | Explained Maths | Leetcode 2338 | MIK • codestorywithMIK • 8,620 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count the Number of Ideal Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Beautiful Subarrays

Next

Count Ways to Make Array With Product