Skip to content

3339. Find the Number of K-Even Arrays

Approach 1: 2D DP

  • Time: $O(nk)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int countOfArrays(int n, int m, int k) {
    constexpr int kMod = 1'000'000'007;
    const int even = m / 2;    // the number of even numbers in [1, m]
    const int odd = m - even;  // the number of odd numbers in [1, m]
    // dp[i][j][0/1] := the number of arrays of length i with j consecutive even
    // number pairs ending in an even number (0) or an odd number (1)
    vector<vector<vector<int>>> dp(n + 1,
                                   vector<vector<int>>(k + 1, vector<int>(2)));

    // Base case: arrays of length 1
    // For an array of length 1, we can't have any even number pairs yet.
    dp[1][0][0] = even;
    dp[1][0][1] = odd;

    for (int i = 2; i <= n; ++i)
      for (int j = 0; j <= k; ++j) {
        // 1. Appending an even number to an array ending in an even number
        //    creates a new consecutive even number pair.
        // 2. Appending an even number to an array ending in an odd number.
        dp[i][j][0] =
            (static_cast<long>(j > 0 ? dp[i - 1][j - 1][0] : 0) * even +
             static_cast<long>(dp[i - 1][j][1]) * even) %
            kMod;
        // 3. Appending an odd number to an array.
        dp[i][j][1] =
            static_cast<long>(dp[i - 1][j][0] + dp[i - 1][j][1]) * odd % kMod;
      }

    return (dp[n][k][0] + dp[n][k][1]) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int countOfArrays(int n, int m, int k) {
    final int MOD = 1_000_000_007;
    final int even = m / 2;   // the number of even numbers in [1, m]
    final int odd = m - even; // the number of odd numbers in [1, m]
    // dp[i][j][0/1] := the number of arrays of length i with j consecutive even
    // number pairs ending in an even number (0) or an odd number (1)
    int[][][] dp = new int[n + 1][k + 1][2];

    // Base case: arrays of length 1
    // For an array of length 1, we can't have any even number pairs yet.
    dp[1][0][0] = even;
    dp[1][0][1] = odd;

    for (int i = 2; i <= n; ++i)
      for (int j = 0; j <= k; ++j) {
        // 1. Appending an even number to an array ending in an even number
        //    creates a new consecutive even number pair.
        // 2. Appending an even number to an array ending in an odd number.
        dp[i][j][0] = (int) (((long) (j > 0 ? dp[i - 1][j - 1][0] : 0) * even +
                              (long) dp[i - 1][j][1] * even) %
                             MOD);
        // 3. Appending an odd number to an array.
        dp[i][j][1] = (int) ((long) (dp[i - 1][j][0] + dp[i - 1][j][1]) * odd % MOD);
      }

    return (dp[n][k][0] + dp[n][k][1]) % MOD;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def countOfArrays(self, n: int, m: int, k: int) -> int:
    MOD = 10**9 + 7
    even = m // 2  # the number of even numbers in [1, m]
    odd = m - even  # the number of odd numbers in [1, m]
    # dp[i][j][0/1] := the number of arrays of length i with j consecutive even
    # number pairs ending in an even number (0) or an odd number (1)
    dp = [[[0] * 2
          for _ in range(k + 1)]
          for _ in range(n + 1)]

    # Base case: arrays of length 1
    # For an array of length 1, we can't have any even number pairs yet.
    dp[1][0][0] = even
    dp[1][0][1] = odd

    for i in range(2, n + 1):
      for j in range(k + 1):
        # 1. Appending an even number to an array ending in an even number
        #    creates a new consecutive even number pair.
        # 2. Appending an even number to an array ending in an odd number.
        dp[i][j][0] = ((dp[i - 1][j - 1][0] if j > 0 else 0) * even +
                       dp[i - 1][j][1] * even) % MOD
        # 3. Appending an odd number to an array.
        dp[i][j][1] = sum(dp[i - 1][j]) * odd % MOD

    return sum(dp[n][k]) % MOD

Approach 2: 1D DP

  • Time: $O(nk)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int countOfArrays(int n, int m, int k) {
    constexpr int kMod = 1'000'000'007;
    const int even = m / 2;    // the number of even numbers in [1, m]
    const int odd = m - even;  // the number of odd numbers in [1, m]
    // dp[j][0/1] := the number of arrays of length so far i with j consecutive
    // even number pairs ending in an even number (0) or an odd number (1)
    vector<vector<int>> dp(k + 1, vector<int>(2));

    // Base case: arrays of length 1
    // For an array of length 1, we can't have any even number pairs yet.
    dp[0][0] = even;
    dp[0][1] = odd;

    for (int i = 2; i <= n; ++i) {
      vector<vector<int>> newDp(k + 1, vector<int>(2));
      for (int j = 0; j <= k; ++j) {
        // 1. Appending an even number to an array ending in an even number
        //    creates a new consecutive even number pair.
        // 2. Appending an even number to an array ending in an odd number.
        newDp[j][0] = (static_cast<long>(j > 0 ? dp[j - 1][0] : 0) * even +
                       static_cast<long>(dp[j][1]) * even) %
                      kMod;
        // 3. Appending an odd number to an array.
        newDp[j][1] = static_cast<long>(dp[j][0] + dp[j][1]) * odd % kMod;
      }
      dp = std::move(newDp);
    }

    return (dp[k][0] + dp[k][1]) % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public int countOfArrays(int n, int m, int k) {
    final int MOD = 1_000_000_007;
    final int even = m / 2;   // the number of even numbers in [1, m]
    final int odd = m - even; // the number of odd numbers in [1, m]
    // dp[j][0/1] := the number of arrays of length so far i with j consecutive
    // even number pairs ending in an even number (0) or an odd number (1)
    int[][] dp = new int[k + 1][2];

    // Base case: arrays of length 1
    // For an array of length 1, we can't have any even number pairs yet.
    dp[0][0] = even;
    dp[0][1] = odd;

    for (int i = 2; i <= n; ++i) {
      int[][] newDp = new int[k + 1][2];
      for (int j = 0; j <= k; ++j) {
        // 1. Appending an even number to an array ending in an even number
        //    creates a new consecutive even number pair.
        // 2. Appending an even number to an array ending in an odd number.
        newDp[j][0] =
            (int) (((long) (j > 0 ? dp[j - 1][0] : 0) * even + (long) dp[j][1] * even) % MOD);
        // 3. Appending an odd number to an array.
        newDp[j][1] = (int) ((long) (dp[j][0] + dp[j][1]) * odd % MOD);
      }
      dp = newDp;
    }

    return (dp[k][0] + dp[k][1]) % MOD;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def countOfArrays(self, n: int, m: int, k: int) -> int:
    MOD = 10**9 + 7
    even = m // 2  # the number of even numbers in [1, m]
    odd = m - even  # the number of odd numbers in [1, m]
    # dp[j][0/1] := the number of arrays of length so far i with j consecutive
    # even number pairs ending in an even number (0) or an odd number (1)
    dp = [[0] * 2 for _ in range(k + 1)]

    # Base case: arrays of length 1
    # For an array of length 1, we can't have any even number pairs yet.
    dp[0][0] = even
    dp[0][1] = odd

    for _ in range(2, n + 1):
      newDp = [[0] * 2 for _ in range(k + 1)]
      for j in range(k + 1):
        # 1. Appending an even number to an array ending in an even number
        #    creates a new consecutive even number pair.
        # 2. Appending an even number to an array ending in an odd number.
        newDp[j][0] = ((dp[j - 1][0] if j > 0 else 0) * even +
                       dp[j][1] * even) % MOD
        # 3. Appending an odd number to an array.
        newDp[j][1] = sum(dp[j]) * odd % MOD
      dp = newDp

    return sum(dp[k]) % MOD