Problem Statement
Farmer John had N cows numbered 0 to N-1. One day he saw K cows running away from his farm. Fox Brus computed the sum of the numbers of the escaped cows. She only told John that the sum was divisible by N. In simple terms, given N & K. Where N denotes total number of cows and K is the total number of cows ran away. Find the total set with length K whose sum is divisible by N.
Flow of Idea
It’s clearly a dynamic programming problem, but coming up with states isn’t that direct. States denotes Sum with length K for ith number. \(formula: dp[i][sum+j][k] = dp[i-1][sum+j][k] + dp[i-1][sum][k-1]\) In words, the values of current state is equal to summation of previous state plus number of ways of adding the ith value.
Code
public class TheCowDivTwo {
private static final int MOD = 1000000007;
public int find(int N, int K) {
int[][][] dp = new int[2][1001][50];
dp[0][0][0] = 1;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
dp[(i + 1) % 2][j][0] = dp[i % 2][j][0];
for (int k = 1; k <= K; k++)
dp[(i + 1) % 2][(j + i) % N][k] = (dp[i % 2][(j + i) % N][k] + dp[i % 2][j][k - 1]) % MOD;
}
return dp[N % 2][0][K];
}
}