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)]))

526 - Beautiful Arrangement

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions