# Calculate if a move is valid

• Essentially a tree traversal (dfs), but only start from 1, 2 and 5 (since some numbers mirror each other [1,3,7,9] [2,4,6,8] [5], and generate same numbers of patterns).

The interesting part I wanted to highlight here is the way of determining if we can go to a certain number. We can of course build a "skip" or "bad" array as many suggested, but it can actually be calculated, see function below for details.

``````public class Solution {

// leverage the fact that some numbers mirror each other [1,3,7,9] [2,4,6,8] [5]
public int numberOfPatterns(int m, int n) {
int res = 0;
boolean[] visit = new boolean[10];

int[] count = new int[1];
traverse(1, m, n, 1, count, visit);
res += 4 * count[0];

count[0] = 0;
traverse(2, m, n, 1, count, visit);
res += 4 * count[0];

count[0] = 0;
traverse(5, m, n, 1, count, visit);
res += count[0];

return res;
}

private void traverse(int start, int m, int n, int depth, int[] count, boolean[] visit) {
if (visit[start]) return;
visit[start] = true;
if (depth >= m && depth <= n) count[0]++;
if (depth < n) {
for (int i=1; i<=9; i++) {
if (i == start) continue;
if (!valid(start, i, visit)) continue;
traverse(i, m, n, depth+1, count, visit);
}
}
visit[start] = false;
}

private boolean valid(int a, int b, boolean[] visit) {
// if either one is 5, always valid
if (a == 5 || b == 5) return true;

// both odd: crossing sum/2
if ((a&1) == 1 && (b&1)==1) {
return visit[(a+b)/2];
}

// both even, and sum/2 is 5: crossing 5
if ((a&1) == 0 && (b&1)==0 && (a+b)/2 == 5) {
return visit[5];
}

// otherwise, always valid
return true;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.