We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Number of Balanced Permutations

Difficulty: Hard

Problem Description

You are given a string num. A string of digits is called balanced if the sum of the digits at even indices is equal to the sum of the digits at odd indices. Return the number of distinct permutations of num that are balanced. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • A balanced permutation has equal sums of digits at even and odd indices.
  • Distinct permutations can be calculated considering the frequency of digits to avoid duplicates.
  • The problem can be approached using combinatorial mathematics to count valid distributions of digits.

Space and Time Complexity

Time Complexity: O(n! / (c1! * c2! * ... * ck!)) where ci are the counts of each distinct digit in the string.
Space Complexity: O(n) for storing frequency counts of the digits.

Solution

The solution involves generating permutations of the digits in the string while ensuring that the sums of the digits at even and odd indices remain equal. We can use combinatorial counting to find the number of valid distributions of digits that satisfy this condition.

  1. Count the frequency of each digit in the string.
  2. Use a recursive backtracking approach to generate permutations, while maintaining a running total of sums at even and odd indices.
  3. Whenever a valid permutation is found (i.e., when the even and odd sums are equal), increment the count.
  4. To avoid counting duplicates, we keep track of the frequency of each digit used in the current permutation.

By employing this strategy, we can efficiently calculate the number of distinct balanced permutations.

Code Solutions

def countBalancedPermutations(num: str) -> int:
    from collections import Counter
    from math import factorial

    MOD = 10**9 + 7

    # Function to calculate n! / (c1! * c2! * ... * ck!)
    def count_permutations(freq):
        denom = 1
        total = sum(freq.values())
        for count in freq.values():
            denom = (denom * factorial(count)) % MOD
        return factorial(total) // denom

    # Function to check if a permutation is balanced
    def is_balanced(permutation):
        even_sum = sum(int(permutation[i]) for i in range(0, len(permutation), 2))
        odd_sum = sum(int(permutation[i]) for i in range(1, len(permutation), 2))
        return even_sum == odd_sum

    freq = Counter(num)
    total_permutations = count_permutations(freq)

    # Generate all distinct permutations and check for balance
    from itertools import permutations
    distinct_permutations = set(permutations(num))
    balanced_count = sum(1 for perm in distinct_permutations if is_balanced(perm))

    return balanced_count % MOD
← Back to All Questions