Beat 100% so far, Java simple solution


  • 1

    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) {
                        arr[i].add(j);
                    }
                }
            }
            
            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) {
                        tmp.add(1 << (j-1));
                    }
                }
                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;
        }
    }
    

  • 1

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


  • 0

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


  • 2

    @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) {
                        tmp.add(1 << (j-1));
                    }
                }
                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;
        }
    }
    

  • 0

    @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) {
                        tmp.add(1 << j);
                    }
                }
                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;
        }
    }
    

  • 0

    @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.


  • 0

    @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.


  • 0

    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?


  • 0
    D

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


Log in to reply
 

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