Welcome to Subscribe On Youtube

Java

  • /**
    
     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++;
                }
            }
        }
    
    }
    
  • // 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)]))
    
    

Java

  • 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;
                    }
                }
            }
        }
    }
    
  • // 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)]))
    
    

All Problems

All Solutions