Скачать или смотреть # 09.05.2025 [3343. Count Number of Balanced Permutations]

09.05.2025
[3343. Count Number of Balanced Permutations](https://leetcode.com/problems/count-n...) hard
[blog post](https://leetcode.com/problems/count-n...)
[substack](https://open.substack.com/pub/dmitrii...)
[youtube](   • # 09.05.2025 [3343. Count Number of Balanc...  )

#### Join me on Telegram

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

#### Problem TLDR

Permutations of even-odd position sums equal #hard #dp #math

#### Intuition

Didn't solved.
Chain-of-thoughts (mostly irrelevant):

```j
// 80^80 (will TLE)
// digits are uniq
// partition into 2 buckets size/2
// 123 12 3
// 12342 132 42
// i.i.i
// let's brute force first
// permutation: can take next any
// we only have 10 digits: 0,1,2,3,4,5,6,7,8,9
// we can count them first
// every even frequency is good to split -- count must be equal
// every odd frequency should be brute-forced
// 18 minutes
// we can calc a sum, then search for a bag of digits to match sum / 2
// 28 minutes
// 44 minutes, idea of bugs is not working for 112, a = 2, b = 11
// the problem with duplicates "11" - not considered a permutation
// 55 minutes, idea to keep both halves in bags
// 60 minutes: wrong answer for 53374 4 instead of 6
// looking for hints:
// freq (known)
// dp (somewhat known)
// useless?
// 1:15 look for solution
```

Working solution:
for every digit `i = 9..0`
take up to `j = frequency[i]` numbers on the one half
another half would contain `frequency[i] - j` automatically
sum would change by `i * j` digit times how many we take
search for the final condition

Now the interesting part - combinatorics. How many permutations we have?
we take `x` digits and place it at odd positions - that is `Combinations(x, o)`
and another half `Combinations(frequency[i] - x, e)`

How to count combinations C(a, b)?
precompute `C[A][B]` like this: `i in 0..a, j in 1..i, c[i][j] = c[i - 1][j] + c[i - 1][j - 1]` (just remember, but better to gain an intuition why it is: permutation is c[i] += c[i - 1], Pascal triangle is computing over previos row, and why it is relevant https://www.perplexity.ai/search/why-...)


#### Approach

gave up after 1hr
whats missing: combinatorics intuition

#### Complexity

Time complexity:
$$O(n^3)$$

Space complexity:
$$O(n^3)$$

#### Code

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