# 22.04.2025 [2338. Count the Number of Ideal Arrays]

22.04.2025
[2338. Count the Number of Ideal Arrays](https://leetcode.com/problems/count-t...) hard
[blog post](https://leetcode.com/problems/count-t...)
[substack](https://open.substack.com/pub/dmitrii...)
[youtube](   • # 22.04.2025 [2338. Count the Number of Id...  )

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppab...

#### Problem TLDR

Arrays a[i] % a[i - 1] == 0, i..n, a[i]..max #hard #combinatorics

#### Intuition

Didn't solve. And didn't understand the solution.
To make it work you have to be fluent with combinatorics.
You have to be fluent with `Stars and bars` https://cp-algorithms.com/combinatori....

My thoughts rundown is irrelevant here, so I will not post it.

Some thoughts about the solution:
arrays are `aaa | bbb | ccc`, where `|` is the bars. `1 | 2 | 4 4` or `1 1| 2 |4` or `1 | 2 2 | 4`.
the max uniq sequence length is for `2`: `1,2,4,8,2^4,2^5,...2^i,..10000`, max i is 2^13=8192 .. 10000
res += `n choose k`, n in `1..maxValue`, k in `0..13`. We considering placing `1..maxValue` numbers into a length of `0..13` places


#### Approach

maybe I should try more combinatorics problems to better understand them; right now they are not picturing in my brain canvas

#### Complexity

Time complexity:
$$O(nlog(n))$$

Space complexity:
$$O(nlog(n))$$

#### Code
https://dmitrysamoylenko.com/2023/07/...