Skip to content

← leetcode

Count Number of Balanced Permutations

· Hard

LeetCode problem 3343

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:

  • since we care about the sums of numbers placed in the odd and even positions, we know if the sum of digits at both positions were equal, then they should both be equal to half of the sum of all digits

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:

  • iterating through the dp matrix backwards (to prevent duplicate calculations) and running the equation dp[i][j]=(dp[i][j]+dp[i−number][j−1])%MODdp[i][j] = (dp[i][j] + dp[i-number][j-1]) \% MOD
    • this works since we view each index dp[i][j] as the number of ways you can reach the sum i with only j numbers
  • however, for each valid numbering, this dp matrix does not consider possible reorderings of each valid numbering

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

  • for example, for each valid selection of numbers, realise that we have TargetLength numbers on the even position and n - TargetLength numbers on the odd position
    • therefore, theoretically there exists (TargetLength)! and (n - TargetLength)! possible orderings of both sets of numbers
  • however, this does not take into account duplicates
    • therefore, we have to keep track of the frequency of each number using a hashmap, and then using the frequency of each number, we can simply divide the total selection by (frequency)!

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×⌊xi⌋+(x%i)x = i \times \left\lfloor \frac{x}{i} \right\rfloor + (x\%i)

then, we can simply rearrage the equation a few times to get:

x=i×⌊xi⌋+(x%i)  ⟹  i×⌊xi⌋+(x%i)≡0 mod x  ⟺  x%i≡−i×⌊xi⌋ mod x  ⟺  1≡−i×⌊xi⌋×(x%i)−1 mod x  ⟺  i−1≡−⌊xi⌋×(x%i)−1 mod x  ⟺  i−1≡x−⌊xi⌋×(x%i)−1 mod x\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

  • Time: O(n * floor(n/2) * floor(m/2)) where n is the length of nums and m is the sum of all the digits in nums
  • Space: O(floor(n/2)*floor(m/2) + n)

learnings