Welcome to Subscribe On Youtube

3339. Find the Number of K-Even Arrays 🔒

Description

You are given three integers n, m, and k.

An array arr is called k-even if there are exactly k indices such that, for each of these indices i (0 <= i < n - 1):

• (arr[i] * arr[i + 1]) - arr[i] - arr[i + 1] is even.

Return the number of possible k-even arrays of size n where all elements are in the range [1, m].

Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 3, m = 4, k = 2

Output: 8

Explanation:

The 8 possible 2-even arrays are:

• [2, 2, 2]
• [2, 2, 4]
• [2, 4, 2]
• [2, 4, 4]
• [4, 2, 2]
• [4, 2, 4]
• [4, 4, 2]
• [4, 4, 4]

Example 2:

Input: n = 5, m = 1, k = 0

Output: 1

Explanation:

The only 0-even array is [1, 1, 1, 1, 1].

Example 3:

Input: n = 7, m = 7, k = 5

Output: 5832

 

Constraints:

• 1 <= n <= 750
• 0 <= k <= n - 1
• 1 <= m <= 1000

Solutions

Solution 1: Memoization Search

Given the numbers $[1, m]$, there are $\textit{cnt0} = \lfloor \frac{m}{2} \rfloor$ even numbers and $\textit{cnt1} = m - \textit{cnt0}$ odd numbers.

We design a function $\textit{dfs}(i, j, k)$, which represents the number of ways to fill up to the $i$-th position, with $j$ remaining positions needing to satisfy the condition, and the parity of the last position being $k$, where $k = 0$ indicates the last position is even, and $k = 1$ indicates the last position is odd. The answer is $\textit{dfs}(0, k, 1)$.

The execution logic of the function $\textit{dfs}(i, j, k)$ is as follows:

• If $j < 0$, it means the remaining positions are less than $0$, so return $0$;
• If $i \ge n$, it means all positions are filled. If $j = 0$, it means the condition is satisfied, so return $1$, otherwise return $0$;
• Otherwise, we can choose to fill with an odd or even number, calculate the number of ways for both, and return their sum.

The time complexity is $O(n \times k)$, and the space complexity is $O(n \times k)$. Here, $n$ and $k$ are the parameters given in the problem.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      private Integer[][][] f;
      private long cnt0, cnt1;
      private final int mod = (int) 1e9 + 7;
  
      public int countOfArrays(int n, int m, int k) {
          f = new Integer[n][k + 1][2];
          cnt0 = m / 2;
          cnt1 = m - cnt0;
          return dfs(0, k, 1);
      }
  
      private int dfs(int i, int j, int k) {
          if (j < 0) {
              return 0;
          }
          if (i >= f.length) {
              return j == 0 ? 1 : 0;
          }
          if (f[i][j][k] != null) {
              return f[i][j][k];
          }
          int a = (int) (cnt1 * dfs(i + 1, j, 1) % mod);
          int b = (int) (cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0) % mod);
          return f[i][j][k] = (a + b) % mod;
      }
  }
  
  

• class Solution {
  public:
      int countOfArrays(int n, int m, int k) {
          int f[n][k + 1][2];
          memset(f, -1, sizeof(f));
          const int mod = 1e9 + 7;
          int cnt0 = m / 2;
          int cnt1 = m - cnt0;
          auto dfs = [&](auto&& dfs, int i, int j, int k) -> int {
              if (j < 0) {
                  return 0;
              }
              if (i >= n) {
                  return j == 0 ? 1 : 0;
              }
              if (f[i][j][k] != -1) {
                  return f[i][j][k];
              }
              int a = 1LL * cnt1 * dfs(dfs, i + 1, j, 1) % mod;
              int b = 1LL * cnt0 * dfs(dfs, i + 1, j - (k & 1 ^ 1), 0) % mod;
              return f[i][j][k] = (a + b) % mod;
          };
          return dfs(dfs, 0, k, 1);
      }
  };
  
  

• class Solution:
      def countOfArrays(self, n: int, m: int, k: int) -> int:
          @cache
          def dfs(i: int, j: int, k: int) -> int:
              if j < 0:
                  return 0
              if i >= n:
                  return int(j == 0)
              return (
                  cnt1 * dfs(i + 1, j, 1) + cnt0 * dfs(i + 1, j - (k & 1 ^ 1), 0)
              ) % mod
  
          cnt0 = m // 2
          cnt1 = m - cnt0
          mod = 10**9 + 7
          ans = dfs(0, k, 1)
          dfs.cache_clear()
          return ans
  
  

• func countOfArrays(n int, m int, k int) int {
  	f := make([][][2]int, n)
  	for i := range f {
  		f[i] = make([][2]int, k+1)
  		for j := range f[i] {
  			f[i][j] = [2]int{-1, -1}
  		}
  	}
  	const mod int = 1e9 + 7
  	cnt0 := m / 2
  	cnt1 := m - cnt0
  	var dfs func(int, int, int) int
  	dfs = func(i, j, k int) int {
  		if j < 0 {
  			return 0
  		}
  		if i >= n {
  			if j == 0 {
  				return 1
  			}
  			return 0
  		}
  		if f[i][j][k] != -1 {
  			return f[i][j][k]
  		}
  		a := cnt1 * dfs(i+1, j, 1) % mod
  		b := cnt0 * dfs(i+1, j-(k&1^1), 0) % mod
  		f[i][j][k] = (a + b) % mod
  		return f[i][j][k]
  	}
  	return dfs(0, k, 1)
  }
  
  

• function countOfArrays(n: number, m: number, k: number): number {
      const f = Array.from({ length: n }, () =>
          Array.from({ length: k + 1 }, () => Array(2).fill(-1)),
      );
      const mod = 1e9 + 7;
      const cnt0 = Math.floor(m / 2);
      const cnt1 = m - cnt0;
      const dfs = (i: number, j: number, k: number): number => {
          if (j < 0) {
              return 0;
          }
          if (i >= n) {
              return j === 0 ? 1 : 0;
          }
          if (f[i][j][k] !== -1) {
              return f[i][j][k];
          }
          const a = (cnt1 * dfs(i + 1, j, 1)) % mod;
          const b = (cnt0 * dfs(i + 1, j - ((k & 1) ^ 1), 0)) % mod;
          return (f[i][j][k] = (a + b) % mod);
      };
      return dfs(0, k, 1);
  }
  
  

All Problems

All Solutions