# Beat 100% so far, Java simple solution

• First part is my original code, second part is speed-upped by @StefanPochmann.

He speed it up

• from 62 ms to 27 ms by using a HashMap<vis, count>

• from 27ms to 5ms by 1).using `int[] map` instead of `hashmap`; 2).using going downwards strategy; 3).using `int[][] arr` instead of `List<Integer>[] arr`.

He just made this code almost perfect.

``````public class Solution {
Map<Integer, Integer> map = new HashMap();
public int countArrangement(int N) {
List<Integer>[] arr = new List[N + 1]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
arr[i] = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
}
}
}

return helper(arr, 1, 0);
}
private int helper(List<Integer>[] arr, int i, int vis) {
if (map.containsKey(vis)) return map.get(vis);
if (i == arr.length) return 1;
int count = 0;
for (int v : arr[i]) {
if ((vis >> v & 1) == 1) continue;
count += helper(arr, i + 1, vis ^ (1 << v));
}
map.put(vis, count);
return count;
}
}
``````

Below is Stefan's optimized code. Really impressive.

``````public class Solution {
int[] map = new int[1 << 15];
public int countArrangement(int N) {
int[][] arr = new int[N + 1][]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
List<Integer> tmp = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
}
}
arr[i] = new int[tmp.size()];
for (int k = 0; k < arr[i].length; k++)
arr[i][k] = tmp.get(k);
}
Arrays.fill(map, 0, 1 << N, -1);
return helper(arr, N, 0);
}
private int helper(int[][] arr, int i, int vis) {
if (map[vis] >= 0) return map[vis];
if (i == 1) return 1;
int count = 0;
for (int v : arr[i])
if ((vis & v) == 0)
count += helper(arr, i - 1, vis ^ v);
map[vis] = count;
return count;
}
}
``````

• Try memoization by `vis` instead. Probably easier if you make it an `int` instead of a `boolean[]`.

• @StefanPochmann Really nice idea. I updated the answer. And it is much faster now.

• @zhugejunwei I think it went down from about 62 ms to about 27 ms, right? I optimized it a bit further, using arrays, going downwards, and precalculating the shifts. Gets accepted in about 6 ms.

``````public class Solution {
int[] map = new int[1 << 15];
public int countArrangement(int N) {
int[][] arr = new int[N + 1][]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
List<Integer> tmp = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
}
}
arr[i] = new int[tmp.size()];
for (int k = 0; k < arr[i].length; k++)
arr[i][k] = tmp.get(k);
}
Arrays.fill(map, 0, 1 << N, -1);
return helper(arr, N, 0);
}
private int helper(int[][] arr, int i, int vis) {
if (map[vis] >= 0) return map[vis];
if (i == 1) return 1;
int count = 0;
for (int v : arr[i])
if ((vis & v) == 0)
count += helper(arr, i - 1, vis ^ v);
map[vis] = count;
return count;
}
}
``````

• @StefanPochmann

Really nice idea about going downwards, and using a map[] array instead of hashmap to speed up. I just ran your code, it's amazing, only 5ms.

But I have a question, why using `int[][] arr` is slightly faster than `List<Integer>[] arr` even though using `int[][] arr` needs another small loop to assign those values in `List<Integer> tmp` to `arr[i][..]`. It's about 3ms faster.

Maybe this is a little bit simpler? But need more space. I don't know why the code below is nearly 1ms slower than yours, so weird.

``````public class Solution {
int[] map = new int[1 << 16];
public int countArrangement(int N) {
int[][] arr = new int[N + 1][]; // idx : possible vals
// construct all possible choices
for (int i = 1; i <= N; i++) {
List<Integer> tmp = new ArrayList();
for (int j = 1; j <= N; j++) {
if (i % j == 0 || j % i == 0) {
}
}
arr[i] = new int[tmp.size()];
for (int k = 0; k < arr[i].length; k++)
arr[i][k] = tmp.get(k);
}
return helper(arr, N, 0);
}
private int helper(int[][] arr, int i, int vis) {
if (map[vis] > 0) return map[vis];
if (i == 1) return 1;
int count = 0;
for (int v : arr[i])
if ((vis & v) == 0)
count += helper(arr, i - 1, vis ^ v);
map[vis] = count;
return count;
}
}
``````

• @zhugejunwei Arrays are just more native and thus faster than Lists, I'd say. And the preparation is very small compared to the actual search, so it's beneficial to make the search faster. The super tiny amount of extra preparation time doesn't matter.

If your new version is slower than mine, I guess one reason is that `count` can end up as `0`, so you write that into your `map` and it looks like "not computed yet" and you might recompute for the same `vis` several times. Try `map[vis] = count + 1;` with `return map[vis] - 1;`. Or `map[vis] = ~count;` with `if (map[vis] < 0) return ~map[vis];`.

Another reason could be that you create a large `map` every time, regardless of how small `N` is. Try doing `map = new int[2 << N];` inside `countArrangement` instead.

• @StefanPochmann Really nice idea.

The first modification using `count+1` works, it speed up to 5ms.

The second suggestion using `[2<<N]` definitely works, and saves a lot of apace. And maybe it's lucky, I just ran it and got 4ms, I ran your prior solution multiple times but never got 4ms. Anyway, it should be 4-5ms.

• I spent as much time as I can afford and still can't understand the bit manipulation part of this solution, can anyone shed some light? What does `vis` stand for? what, in human language, is stored in the `map`?

• Why does the going downwards works better than the going upwards?

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