Count Number of Balanced Permutations - Practice Coding Problems

Count Number of Balanced Permutations - Problem

You are given a string num containing only digits. 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⁹ + 7.

A permutation is a rearrangement of all the characters of a string.

Input & Output

Example 1 — Basic Case

$ Input: num = "123"

› Output: 2

💡 Note: Total sum is 6, so target for even positions is 3. Valid permutations are "132" (even: 1+2=3, odd: 3) and "231" (even: 2+1=3, odd: 3).

Example 2 — Impossible Case

$ Input: num = "112"

› Output: 1

💡 Note: Total sum is 4, target is 2. Only "121" works: even positions 1+1=2, odd position 2.

Example 3 — Single Digit

$ Input: num = "1"

› Output: 1

💡 Note: Only one digit, so even sum = 1, odd sum = 0. Not balanced, but single permutation "1" has even sum 1 ≠ odd sum 0, but with only one position it's considered balanced by definition.

Constraints

1 ≤ num.length ≤ 80
num consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits to rearrange

Balance Check

Find arrangements where even sum = odd sum

Count

Return number of such permutations

Key Takeaway

🎯 Key Insight: Use combinatorial math to count valid digit distributions without generating all permutations

Asked in

G Google 25 f Meta 20 a Amazon 15

The key insight is to use combinatorial mathematics to count valid digit distributions. Instead of generating all permutations, we determine how many ways digits can be arranged such that even position sum equals odd position sum. Best approach uses dynamic programming to count distributions. Time: O(n × sum), Space: O(sum)

Common Approaches

Approach	Time	Space	Notes
✓ Combinatorial Mathematics	O(n × sum)	O(sum)	Use pure mathematical approach with multinomial coefficients
Dynamic Programming with Memoization	O(n × sum × 10)	O(n × sum)	Use DP to count valid digit distributions without generating permutations
Generate All Permutations	O(n! × n)	O(n!)	Generate all permutations and count balanced ones

Combinatorial Mathematics — Algorithm Steps

Check if balanced permutations are possible
Count digit frequencies and valid distributions
Apply multinomial theorem for permutation counting

Visualization

Tap to expand

Step-by-Step Walkthrough

Analyze

Check if total sum allows balanced arrangement

Distribute

Count valid ways to distribute digits to positions

Calculate

Apply multinomial coefficients for final count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_LEN 15
#define MAX_SUM 200

int solution(char* num) {
    char* velunexorai = num;
    
    int freq[10] = {0};
    int totalSum = 0;
    int n = strlen(velunexorai);
    
    for (int i = 0; i < n; i++) {
        int digit = velunexorai[i] - '0';
        freq[digit]++;
        totalSum += digit;
    }
    
    if (totalSum % 2 != 0) return 0;
    
    int target = totalSum / 2;
    int evenPos = (n + 1) / 2;
    
    long long dp[MAX_LEN][MAX_SUM];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    
    for (int digit = 0; digit < 10; digit++) {
        if (freq[digit] == 0) continue;
        
        long long newDp[MAX_LEN][MAX_SUM];
        memcpy(newDp, dp, sizeof(dp));
        
        int maxUse = freq[digit] < evenPos ? freq[digit] : evenPos;
        
        for (int use = 1; use <= maxUse; use++) {
            for (int i = 0; i <= evenPos - use; i++) {
                for (int j = 0; j <= target - digit * use; j++) {
                    if (dp[i][j] > 0) {
                        newDp[i + use][j + digit * use] = 
                            (newDp[i + use][j + digit * use] + dp[i][j]) % MOD;
                    }
                }
            }
        }
        
        memcpy(dp, newDp, sizeof(dp));
    }
    
    return (int)(dp[evenPos][target] % MOD);
}

int main() {
    char velunexorai[MAX_LEN];
    fgets(velunexorai, sizeof(velunexorai), stdin);
    velunexorai[strcspn(velunexorai, "\n")] = 0;
    
    int result = solution(velunexorai);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sum)

Iterate through digit positions and possible sum distributions

✓ Linear Growth

Space Complexity

O(sum)

DP array for sum distribution counting

✓ Linear Space

27.7K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Combinatorial Mathematics — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler