Start learning free

LESSON 344 OF 414 · DYNAMIC PROGRAMMING

Binary Strings With K Ones On Even Positions in Scala

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

    SCALA · DYNAMIC PROGRAMMING

    Binary Strings With K Ones On Even Positions in Scala, explained

    Problem overview

    The method countBinaryStrings(n, k) counts the binary strings of length n that contain exactly k ones, where every one sits on an even position. Positions are counted from 0, so the even positions are 0, 2, 4 and so on. The notes guarantee 2 * k <= n <= 30.

    For n = 6 and k = 2 the even positions are 0, 2 and 4. The valid strings are 101000 (ones at positions 0 and 2), 100010 (positions 0 and 4) and 001010 (positions 2 and 4), so the answer is 3. The odd positions always hold zeros.

    Approach: decide one character at a time

    A direct count is possible here: the odd positions are fixed, so the problem is really about choosing which k of the even positions get a one. The lesson solves it with the same table method as the plain version of this problem, which carries over to rules that are less regular.

    Let dp(i)(j) be the number of valid prefixes of length i that contain j ones. The table is filled forward: each prefix is extended by the character at position i, and the number of ways is passed on to the longer prefix.

    • A 0 can go at any position and doesn't change the count of ones, so dp(i)(j) flows into dp(i + 1)(j).
    • A 1 may go only at an even i, and only if the prefix still has room for another one, so dp(i)(j) also flows into dp(i + 1)(j + 1) when i is even and j < k.

    Here is the table for n = 6 and k = 2. Each row lists the counts for 0, 1 and 2 ones:

    length 0:  1  0  0
length 1:  1  1  0
length 2:  1  1  0
length 3:  1  2  1
length 4:  1  2  1
length 5:  1  3  3
length 6:  1  3  3

    The rows for lengths 2, 4 and 6 repeat the row before them, because the position just added was odd and could only take a zero. The last row ends in 3, the answer.

    Step by step

    1. Create the table with Array.fill(n + 1, k + 1)(0). The two dimensions come first and the fill value in a second pair of parentheses.
    2. Set dp(0)(0) to 1. The empty prefix is the one starting point.
    3. Loop over the positions with 0 until n. Iteration i decides the character at position i and writes into row i + 1, so the last pass (i = n - 1) writes row n.
    4. Loop over the counts of ones with 0 to k. The upper bound is inclusive because the table has k + 1 columns.
    5. Place a zero: add dp(i)(j) to dp(i + 1)(j). No condition is needed.
    6. Test whether a one is allowed: i % 2 == 0 && j < k.
    7. Place a one: add dp(i)(j) to dp(i + 1)(j + 1).
    8. Return dp(n)(k).

    The solution in Scala

    class Solution {
    def countBinaryStrings(n: Int, k: Int): Int = {
        val dp = Array.fill(n + 1, k + 1)(0)
        dp(0)(0) = 1
        for (i <- 0 until n) {
            for (j <- 0 to k) {
                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)
    }
}

    Some Scala details in this code:

    • Array.fill(n + 1, k + 1)(0) takes the dimensions in the first parameter list and the value in the second. The value is evaluated for each cell, and the result is an Array[Array[Int]] with separate rows.
    • += on an array element. dp(i + 1)(j) += dp(i)(j) is shorthand for dp(i + 1)(j) = dp(i + 1)(j) + dp(i)(j). Scala rewrites it into a call to update, so it works on array cells even though dp is a val.
    • 0 until n against 0 to k. The first excludes its end and the second includes it. The positions run up to n - 1 because the code writes to i + 1, while the counts run up to k because k is a valid column.
    • && short-circuits. When i is odd, the second half of the condition isn't evaluated.
    • % with non-negative numbers behaves as expected. i is never negative here, so i % 2 == 0 is a safe parity test.

    Complexity

    Time: O(n * k). The two loops visit about n * (k + 1) cells, each with a constant amount of work.

    Space: O(n * k). The table has (n + 1) * (k + 1) cells.

    Edge cases and common mistakes

    • Dropping the j < k check. When j equals k, dp(i + 1)(j + 1) is past the last column and the method throws an ArrayIndexOutOfBoundsException. The check also stops strings with more than k ones from being counted.
    • Using 1-based positions. If position 1 were treated as the first position, the even test would pick the wrong characters. With i starting at 0, the test i % 2 == 0 matches the example: ones at positions 0, 2 and 4.
    • k = 0. Only the all-zeros string qualifies. countBinaryStrings(4, 0) returns 1.
    • The boundary of the notes. With n = 5 and k = 3 the even positions 0, 2 and 4 must all hold ones, and the method returns 1. For n = 4 and k = 3, which the notes rule out, there are only two even positions and the method returns 0.
    • Largest input. For n = 30 and k = 15 all fifteen even positions are used, and the answer is 1. Counts never get near the Int limit here, because there are at most 15 positions to choose from.
    • Skipping the zero update. If only the "place a one" branch ran, the table could not carry a prefix across an odd position, and the counts would drop to 0.

    Testing

    • n = 6, k = 2 gives 3.
    • n = 4, k = 1 gives 2.
    • n = 4, k = 0 gives 1.
    • n = 5, k = 3 gives 1.
    • n = 30, k = 15 gives 1.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free