Welcome to Subscribe On Youtube

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• /**
  
   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
      }
  }
  
  

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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