Yet another Java recursive solution, using bit mask (7ms)


  • 0
    J

    Number i has already been used, if i - 1 th bit is 1 in taken
    Using this bit representation, we can iterate through available numbers, instead of entire numbers.

    public class Solution {
        private int helper(int ind, int max, int taken) {
            if (ind < 2) return 1;
            int res = 0;
            int available = ~taken & ((1 << max) - 1);
            while (available > 0) {
                int i = 1 + Integer.numberOfTrailingZeros(available);
                if (i % ind == 0 || ind % i == 0) {
                    res += helper(ind - 1, max, taken ^ (1 << (i - 1)));
                }
                available &= available - 1;
            }
            return res;
        }
        public int countArrangement(int N) {
            return helper(N, N, 0);
        }
    }
    

Log in to reply
 

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