Binary Strings with Equal Sum of Two Halves

Time: O(n)

Space: O(n)

Intuition

A binary string of length 2n splits into two halves of length n. Equal sum means both halves contain the same number of 1s. If the first half has k ones, choose their positions in C(n, k) ways and independently choose k ones in the second half in another C(n, k) ways. Summing C(n, k)^2 over all k yields the closed form C(2n, n).

Algorithm

1Precompute factorials fact[i] = i! modulo MOD up to 2n.
2Compute numerator = fact[2n].
3Compute denominator = fact[n] * fact[n] modulo MOD.
4Return numerator * denominator^(MOD - 2) modulo MOD using fast modular exponentiation.

Example Walkthrough

Input: n = 1

1.Binary strings of length 2 are "00", "01", "10", "11".
2.Equal halves require the same number of 1s in each half of length 1.
3.Valid strings are "00" and "11", so the count is 2.
4.Formula check: C(2, 1) = 2.

Output: 2

Common Pitfalls

•Equal sum for binary strings means equal count of 1s, not equal numeric value of the substring.
•Use modular inverse via Fermat: a^(-1) = a^(MOD - 2) when MOD is prime.
•Precompute factorials only up to 2n, not higher.

Binary Strings with Equal Sum of Two Halves.java

Java

// Approach: Equal halves means equal number of 1s in each half of length n. For k ones in the
// first half and k in the second, there are C(n,k)^2 strings; summing over k gives C(2n, n).
// Time: O(n) Space: O(n)

class Solution {

    public int computeValue(int n) {
        long[] fact = new long[2 * n + 1];
        fact[0] = 1;

        for (int i = 1; i <= 2 * n; i++) {
            fact[i] = (fact[i - 1] * i) % MOD;
        }

        long numerator = fact[2 * n];
        long denominator = (fact[n] * fact[n]) % MOD;

        long ans = (numerator * power(denominator, MOD - 2)) % MOD;

        return (int) ans;
    }

    static final long MOD = 1000000007L;

    long power(long a, long b) {
        long res = 1;
        a %= MOD;

        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * a) % MOD;
            }
            a = (a * a) % MOD;
            b >>= 1;
        }
        return res;
    }
}

Was this solution helpful?