Welcome to Subscribe On Youtube
  • /**
    
     Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:
    
     The number at the ith position is divisible by i.
     i is divisible by the number at the ith position.
     Now given N, how many beautiful arrangements can you construct?
    
     Example 1:
     Input: 2
     Output: 2
     Explanation:
    
     The first beautiful arrangement is [1, 2]:
    
     Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).
    
     Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).
    
     The second beautiful arrangement is [2, 1]:
    
     Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).
    
     Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
     Note:
     N is a positive integer and will not exceed 15.
    
     */
    
    public class Beautiful_Arrangement {
    
    
        public class Solution_trim {
            int count = 0;
            public int countArrangement(int N) {
                int[] nums = new int[N];
                for (int i = 1; i <= N; i++)
                    nums[i - 1] = i;
                permute(nums, 0);
                return count;
            }
            public void permute(int[] nums, int l) {
                if (l == nums.length) {
                    count++;
                }
                for (int i = l; i < nums.length; i++) {
                    swap(nums, i, l);
    
                    // @note: only the current index is ok, then add it
                    if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                        permute(nums, l + 1);
                    }
                    swap(nums, i, l);
                }
            }
            public void swap(int[] nums, int x, int y) {
                int temp = nums[x];
                nums[x] = nums[y];
                nums[y] = temp;
            }
        }
    
        public class Solution {
            int count = 0;
            public int countArrangement(int N) {
    
                if (N < 0) {
                    return count;
                }
    
                int[] nums = new int[N];
                for (int i = 1; i <= N; i++) {
                    nums[i - 1] = i;
                }
    
                permute(nums, 0);
    
                return count;
            }
    
            public void permute(int[] nums, int l) {
                if (l == nums.length - 1) {
                    isBeautiful(nums);
                }
    
                for (int i = l; i < nums.length; i++) {
                    swap(nums, i, l);
                    permute(nums, l + 1);
                    swap(nums, i, l);
                }
            }
    
            public void swap(int[] nums, int x, int y) {
                int temp = nums[x];
                nums[x] = nums[y];
                nums[y] = temp;
            }
    
            private void isBeautiful (int[] nums) {
                int i;
                for (i = 1; i <= nums.length; i++) {
                    if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0)
                        break;
                }
                if (i == nums.length + 1) {
                    count++;
                }
            }
        }
    
    }
    
    ############
    
    class Solution {
        public int countArrangement(int N) {
            int maxn = 1 << N;
            int[] f = new int[maxn];
            f[0] = 1;
            for (int i = 0; i < maxn; ++i) {
                int s = 1;
                for (int j = 0; j < N; ++j) {
                    s += (i >> j) & 1;
                }
                for (int j = 1; j <= N; ++j) {
                    if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
                        f[i | (1 << (j - 1))] += f[i];
                    }
                }
            }
            return f[maxn - 1];
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/beautiful-arrangement/
    // Time: O(K) where K is the number of valid permuataions
    // Space: O(N)
    class Solution {
        int dfs(vector<int> &v, int start) {
            if (start == v.size()) return 1;
            int ans = 0;
            for (int i = start; i < v.size(); ++i) {
                if (v[i] % (start + 1) && (start + 1) % v[i]) continue;
                swap(v[i], v[start]);
                ans += dfs(v, start + 1);
                swap(v[i], v[start]);
            }
            return ans;
        }
    public:
        int countArrangement(int n) {
            vector<int> v(n);
            iota(begin(v), end(v), 1);
            return dfs(v, 0);
        }
    };
    
  • class Solution:
        def countArrangement(self, n: int) -> int:
            def dfs(i):
                nonlocal ans, n
                if i == n + 1:
                    ans += 1
                    return
                for j in match[i]:
                    if not vis[j]:
                        vis[j] = True
                        dfs(i + 1)
                        vis[j] = False
    
            ans = 0
            vis = [False] * (n + 1)
            match = defaultdict(list)
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if j % i == 0 or i % j == 0:
                        match[i].append(j)
    
            dfs(1)
            return ans
    
    ############
    
    class Solution(object):
      def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
    
        def dfs(pos, unused):
          if len(unused) == 0:
            return 1
          ret = 0
          for num in list(unused):
            if pos % num == 0 or num % pos == 0:
              unused -= {num}
              ret += dfs(pos + 1, unused)
              unused |= {num}
          return ret
    
        return dfs(1, set([i for i in range(1, N + 1)]))
    
    
  • func countArrangement(n int) int {
    	ans := 0
    	match := make(map[int][]int)
    	for i := 1; i <= n; i++ {
    		for j := 1; j <= n; j++ {
    			if i%j == 0 || j%i == 0 {
    				match[i] = append(match[i], j)
    			}
    		}
    	}
    	vis := make([]bool, n+1)
    
    	var dfs func(i int)
    	dfs = func(i int) {
    		if i == n+1 {
    			ans++
    			return
    		}
    		for _, j := range match[i] {
    			if !vis[j] {
    				vis[j] = true
    				dfs(i + 1)
    				vis[j] = false
    			}
    		}
    	}
    
    	dfs(1)
    	return ans
    }
    
  • function countArrangement(n: number): number {
        const vis = new Array(n + 1).fill(0);
        const match = Array.from({ length: n + 1 }, () => []);
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                if (i % j === 0 || j % i === 0) {
                    match[i].push(j);
                }
            }
        }
    
        let res = 0;
        const dfs = (i: number, n: number) => {
            if (i === n + 1) {
                res++;
                return;
            }
            for (const j of match[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    dfs(i + 1, n);
                    vis[j] = false;
                }
            }
        };
        dfs(1, n);
        return res;
    }
    
    
  • impl Solution {
        fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
            if i == n + 1 {
                *res += 1;
                return;
            }
            for &j in mat[i].iter() {
                if !vis[j] {
                    vis[j] = true;
                    Self::dfs(i + 1, n, mat, vis, res);
                    vis[j] = false;
                }
            }
        }
    
        pub fn count_arrangement(n: i32) -> i32 {
            let n = n as usize;
            let mut vis = vec![false; n + 1];
            let mut mat = vec![Vec::new(); n + 1];
            for i in 1..=n {
                for j in 1..=n {
                    if i % j == 0 || j % i == 0 {
                        mat[i].push(j);
                    }
                }
            }
    
            let mut res = 0;
            Self::dfs(1, n, &mat, &mut vis, &mut res);
            res
        }
    }
    
    
  • class Solution {
        int count = 0;
    
        public int countArrangement(int N) {
            if (N == 0)
                return 0;
            boolean[] used = new boolean[N + 1];
            backtrack(N, 1, used);
            return count;
        }
    
        public void backtrack(int N, int position, boolean[] used) {
            if (position > N)
                count++;
            else {
                for (int i = 1; i <= N; i++) {
                    if (!used[i] && (i % position == 0 || position % i == 0)) {
                        used[i] = true;
                        backtrack(N, position + 1, used);
                        used[i] = false;
                    }
                }
            }
        }
    }
    
    ############
    
    class Solution {
        public int countArrangement(int N) {
            int maxn = 1 << N;
            int[] f = new int[maxn];
            f[0] = 1;
            for (int i = 0; i < maxn; ++i) {
                int s = 1;
                for (int j = 0; j < N; ++j) {
                    s += (i >> j) & 1;
                }
                for (int j = 1; j <= N; ++j) {
                    if (((i >> (j - 1) & 1) == 0) && (s % j == 0 || j % s == 0)) {
                        f[i | (1 << (j - 1))] += f[i];
                    }
                }
            }
            return f[maxn - 1];
        }
    }
    
    
  • // OJ: https://leetcode.com/problems/beautiful-arrangement/
    // Time: O(K) where K is the number of valid permuataions
    // Space: O(N)
    class Solution {
        int dfs(vector<int> &v, int start) {
            if (start == v.size()) return 1;
            int ans = 0;
            for (int i = start; i < v.size(); ++i) {
                if (v[i] % (start + 1) && (start + 1) % v[i]) continue;
                swap(v[i], v[start]);
                ans += dfs(v, start + 1);
                swap(v[i], v[start]);
            }
            return ans;
        }
    public:
        int countArrangement(int n) {
            vector<int> v(n);
            iota(begin(v), end(v), 1);
            return dfs(v, 0);
        }
    };
    
  • class Solution:
        def countArrangement(self, n: int) -> int:
            def dfs(i):
                nonlocal ans, n
                if i == n + 1:
                    ans += 1
                    return
                for j in match[i]:
                    if not vis[j]:
                        vis[j] = True
                        dfs(i + 1)
                        vis[j] = False
    
            ans = 0
            vis = [False] * (n + 1)
            match = defaultdict(list)
            for i in range(1, n + 1):
                for j in range(1, n + 1):
                    if j % i == 0 or i % j == 0:
                        match[i].append(j)
    
            dfs(1)
            return ans
    
    ############
    
    class Solution(object):
      def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
    
        def dfs(pos, unused):
          if len(unused) == 0:
            return 1
          ret = 0
          for num in list(unused):
            if pos % num == 0 or num % pos == 0:
              unused -= {num}
              ret += dfs(pos + 1, unused)
              unused |= {num}
          return ret
    
        return dfs(1, set([i for i in range(1, N + 1)]))
    
    
  • func countArrangement(n int) int {
    	ans := 0
    	match := make(map[int][]int)
    	for i := 1; i <= n; i++ {
    		for j := 1; j <= n; j++ {
    			if i%j == 0 || j%i == 0 {
    				match[i] = append(match[i], j)
    			}
    		}
    	}
    	vis := make([]bool, n+1)
    
    	var dfs func(i int)
    	dfs = func(i int) {
    		if i == n+1 {
    			ans++
    			return
    		}
    		for _, j := range match[i] {
    			if !vis[j] {
    				vis[j] = true
    				dfs(i + 1)
    				vis[j] = false
    			}
    		}
    	}
    
    	dfs(1)
    	return ans
    }
    
  • function countArrangement(n: number): number {
        const vis = new Array(n + 1).fill(0);
        const match = Array.from({ length: n + 1 }, () => []);
        for (let i = 1; i <= n; i++) {
            for (let j = 1; j <= n; j++) {
                if (i % j === 0 || j % i === 0) {
                    match[i].push(j);
                }
            }
        }
    
        let res = 0;
        const dfs = (i: number, n: number) => {
            if (i === n + 1) {
                res++;
                return;
            }
            for (const j of match[i]) {
                if (!vis[j]) {
                    vis[j] = true;
                    dfs(i + 1, n);
                    vis[j] = false;
                }
            }
        };
        dfs(1, n);
        return res;
    }
    
    
  • impl Solution {
        fn dfs(i: usize, n: usize, mat: &Vec<Vec<usize>>, vis: &mut Vec<bool>, res: &mut i32) {
            if i == n + 1 {
                *res += 1;
                return;
            }
            for &j in mat[i].iter() {
                if !vis[j] {
                    vis[j] = true;
                    Self::dfs(i + 1, n, mat, vis, res);
                    vis[j] = false;
                }
            }
        }
    
        pub fn count_arrangement(n: i32) -> i32 {
            let n = n as usize;
            let mut vis = vec![false; n + 1];
            let mut mat = vec![Vec::new(); n + 1];
            for i in 1..=n {
                for j in 1..=n {
                    if i % j == 0 || j % i == 0 {
                        mat[i].push(j);
                    }
                }
            }
    
            let mut res = 0;
            Self::dfs(1, n, &mat, &mut vis, &mut res);
            res
        }
    }
    
    

All Problems

All Solutions