Start learning free

LESSON 319 OF 347 · DYNAMIC PROGRAMMING

Binary Strings With K Ones on Even Positions in C#: 2D DP

Practice O(n * k) Read the full explanation

Given two non-negative integers N and K, return the number of binary strings of length N with exactly K ones placed only on even positions

Example:

Input: N = 6, K = 2
Output: 3
Explanation: [
    "101000",
    "100010",
    "001010"
]
Notes: 2 * K <= N <= 30
STEP 1 OF 8
    Ctrl + Enter to check

    C# · DYNAMIC PROGRAMMING

    Binary Strings With K Ones On Even Positions in C#, explained

    Problem overview

    The method CountBinaryStrings receives two integers, n and k, and returns how many binary strings of length n have exactly k ones, all of them at even positions. Positions are counted from 0, so the even positions are 0, 2, 4 and so on. For n = 6 and k = 2 the answer is 3: 101000, 100010 and 001010. In each, the ones sit at two of the positions 0, 2 and 4. The notes say 2 * k <= n <= 30.

    Approach: decide one position at a time

    Instead of looking at how a string ends, this lesson builds the string from left to right and pushes counts forward. Let dp[i, j] be the number of ways to fill the first i positions so that exactly j ones were placed. From each state, the next position, with index i, offers up to two choices:

    • Place a 0. It is allowed at any position, and the number of ones stays j. So the ways in dp[i, j] flow into dp[i + 1, j].
    • Place a 1. It is allowed only when i is even, and only if fewer than k ones have been placed so far (j < k). The ways flow into dp[i + 1, j + 1].

    The starting state is dp[0, 0] = 1: zero positions filled, zero ones, one way (the empty prefix). After all n positions are decided, dp[n, k] holds the answer.

    Trace n = 4 and k = 1. Positions 0 and 2 may hold the single one, so the answer should be 2. Starting at dp[0, 0] = 1: position 0 gives dp[1, 0] = 1 (a 0) and dp[1, 1] = 1 (a 1). Position 1 is odd, so only zeros move forward: dp[2, 0] = 1 and dp[2, 1] = 1. Position 2 is even: dp[3, 0] = 1, dp[3, 1] = 2, one way from carrying dp[2, 1] forward with a 0 (the one is at position 0) and one from placing a 1 on dp[2, 0] (the one is at position 2). Position 3 is odd and carries the values over: dp[4, 1] = 2.

    Step by step

    1. Declare the table as a rectangular int[,] with n + 1 rows and k + 1 columns. Zero is the default value of every cell.
    2. Set dp[0, 0] = 1 as the single starting state.
    3. Loop over positions i from 0 to n - 1. Each pass fills row i + 1 from row i, so the last pass fills row n.
    4. Loop over the counts j from 0 to k inclusive. Every reachable state has to pass its ways forward.
    5. Place a zero: add dp[i, j] to dp[i + 1, j]. No condition is needed.
    6. Test for a one: the position must be even (i % 2 == 0) and j < k.
    7. Place a one: add dp[i, j] to dp[i + 1, j + 1].
    8. Return dp[n, k].

    The solution in C#

    class Solution {

    public int CountBinaryStrings(int n, int k) {
        int[,] dp = new int[n + 1, k + 1];
        dp[0, 0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i + 1, j] += dp[i, j];
                if (i % 2 == 0 && j < k) {
                    dp[i + 1, j + 1] += dp[i, j];
                }
            }
        }
        return dp[n, k];
    }
}

    C# details worth knowing:

    • The += operator. Two different transitions can reach the same cell: dp[i + 1, j] receives from dp[i, j] (a 0) and from dp[i, j - 1] (a 1). Using += accumulates both, whereas = would overwrite the first contribution.
    • Push versus pull. A table can be filled by computing each cell from earlier cells (pulling), or by having each cell send its value to later cells (pushing). This solution pushes. Both styles give the same table; pushing is natural when the rule is about what can be added next.
    • The guard protects the array. When j == k, dp[i + 1, j + 1] would be column k + 1, which doesn't exist and would throw IndexOutOfRangeException. The condition j < k prevents that, and && evaluates it only after the parity test.
    • Remainder operator. i % 2 == 0 is true for 0, 2, 4. In C# the remainder keeps the sign of the dividend, which doesn't matter here because i is never negative.

    Why the answer is a binomial coefficient

    There is a shortcut worth knowing. The odd positions must hold zeros, and the even positions are free: there are (n + 1) / 2 of them (integer division), and a valid string picks exactly k of them for its ones. So the answer is "choose k from (n + 1) / 2". For n = 6 that is choosing 2 from 3 positions, which is 3. The table computes this count without needing a formula, and it generalises to rules that no formula covers.

    Complexity

    Time: O(n * k), a constant amount of work per cell. Space: O(n * k) for the table, reducible to two rows because each row depends only on the previous one.

    Edge cases and common mistakes

    • k = 0. Only the all-zero string qualifies, and the table gives 1.
    • Counting from 1. The statement's example has ones at the first and third positions of "101000". That is positions 0 and 2 in zero-based terms, which is what the code uses. Treating the first character as position 1 would shift which positions are "even".
    • Dropping the zero transition. Without dp[i + 1, j] += dp[i, j], no string could ever contain a 0, so almost every count would be lost.
    • Using = instead of +=. The one-transition into a cell would erase the zero-transition's contribution.
    • Dropping j < k. The program would crash on the last column.

    Testing

    • n = 6, k = 2 gives 3.
    • n = 4, k = 1 gives 2.
    • n = 4, k = 0 gives 1.
    • n = 6, k = 3 gives 1: ones at positions 0, 2 and 4.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free