3343: Count-Number-of-Balanced-Permutations
Hard 2025-05-09

Holy Cowabunga! I will not even pretend like this question was solved by me without external assistance, but Live Laugh Leetcode amiri-

Anyways, credit to this fellow for the original solution. In all honesty, the steps do make logical sense, however there are some optimisations that caught me off guard.

The baseline algorithm hinges heavily on dynamic programming. The key points you need to realise is:

Therefore, if we let

• the TargetSum be equal to half of the sum of all digits
• the TargetLength be equal to (the floor of) half of num.size(),

we can run a dynamic programming algorithm to calculate the number of ways we can choose TargetLength number of digits to sum up to TargetSum by creating a dp[TargetSum+1][TargetLength+1] array. Then, for each number in nums:

To figure this out, we can bring in some permutations and combinations knowledge. If we now let n be equal to nums.size():

That does not sound too bad, until you realise factorials are humongous, and we have to do this while modularising the answer by 10^9+7.

The genius way of pre-computing modulo inverses comes from this source right here (which was simply presented in the above solution like it was trivial????).

If the modulo is x and i is any integer smaller than x, then we know intuitively that $$x = i \times \left\lfloor \frac{x}{i} \right\rfloor + (x\%i)$$ then, we can simply rearrage the equation a few times to get: $$\begin{align*} &x = i \times \left\lfloor \frac{x}{i} \right\rfloor + (x\%i) \\ &\implies i \times \left\lfloor \frac{x}{i} \right\rfloor + (x\%i) \equiv 0 \bmod x \\ &\iff x\%i \equiv - i \times \left\lfloor \frac{x}{i} \right\rfloor \bmod x \\ &\iff 1 \equiv - i \times \left\lfloor \frac{x}{i} \right\rfloor \times (x\%i)^{-1} \bmod x \\ &\iff i^{-1} \equiv -\left\lfloor \frac{x}{i} \right\rfloor \times (x\%i)^{-1} \bmod x \\ &\iff i^{-1} \equiv x -\left\lfloor \frac{x}{i} \right\rfloor \times (x\%i)^{-1} \bmod x \\ \end{align*}$$

Now, if we make this less math-coded and more cs-coded, the final equation looks something like:

inverse[i] = MOD - (MOD/i) * inverse[MOD%i] % MOD

which makes pre-calculating modular inverses quite trivial and quite fast; only taking O(n).

Code:

class Solution {
    static const int MOD = 1e9+7;
public:
    int countBalancedPermutations(string num) {
        int n = num.size();
        int digits[10] = {0};

        vector<long long> factorial (n+1, 1);
        vector<long long> inv (n+1, 1);
        vector<long long> inv_factorial (n+1, 1);

        for (int i = 2; i <= n; ++i) {
            inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
        }
        for (int i = 1; i <= n; ++i) {
            factorial[i] = factorial[i-1] * i % MOD;
            inv_factorial[i] = inv_factorial[i-1] * inv[i] % MOD;
        }
        
        int sum = 0;
        for (char& n : num) {
            sum += n-'0';
        }

        if (sum%2 == 1) return 0;

        int targetSum = sum/2;
        int targetLength = n/2;
        vector<vector<int>> dp(targetSum+1, vector<int>(targetLength+1));
        dp[0][0] = 1;

        for (char& n : num) {
            int number = n-'0';
            ++digits[number];

            for (int i = targetSum; i >= number; --i) {
                for (int j = targetLength; j > 0; --j) {
                    dp[i][j] = (dp[i][j] + dp[i-number][j-1]) % ((int)1e9 + 7);
                }
            }
        }
        
        long long ans = dp.back().back() * factorial[targetLength] % MOD * factorial[n - targetLength] % MOD;
        for (int& i : digits) {
            ans = ans * inv_factorial[i] % MOD;
        }

        return ans;
    }
};

Complexity:

Learnings: