beautiful-arrangement

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Suppose you have <code>n</code> integers labeled <code>1</code> through <code>n</code>. A permutation of those <code>n</code> integers <code>perm</code> (1-indexed) is considered a beautiful arrangement if for every <code>i</code> (<code>1 &lt;= i &lt;= n</code>), either of the following is true:

<ul>
	<li><code>perm[i]</code> is divisible by <code>i</code>.</li>
	<li><code>i</code> is divisible by <code>perm[i]</code>.</li>
</ul>

Given an integer <code>n</code>, return the number of the beautiful arrangements that you can construct.

&nbsp;
Example 1:

<pre>
Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
 - perm[1] = 1 is divisible by i = 1
 - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
 - perm[1] = 2 is divisible by i = 1
 - i = 2 is divisible by perm[2] = 1
</pre>

Example 2:

<pre>
Input: n = 1
Output: 1
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
</ul>

countArrangement

Beautiful Arrangement

Beautiful Arrangement II

beautiful-arrangement-ii

优美的排列 II

Bit Manipulation

Array

Dynamic Programming

Backtracking

Bitmask

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 <code>perm</code>（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：

<ul>
	<li><code>perm[i]</code> 能够被 <code>i</code> 整除</li>
	<li><code>i</code> 能够被 <code>perm[i]</code> 整除</li>
</ul>

给你一个整数 <code>n</code> ，返回可以构造的 优美排列 的 数量 。

&nbsp;

示例 1：

<pre>
输入：n = 2
输出：2
解释：
第 1 个优美的排列是 [1,2]：
 - perm[1] = 1 能被 i = 1 整除
 - perm[2] = 2 能被 i = 2 整除
第 2 个优美的排列是 [2,1]:
 - perm[1] = 2 能被 i = 1 整除
 - i = 2 能被 perm[2] = 1 整除
</pre>

示例 2：

<pre>
输入：n = 1
输出：1
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 15</code></li>
</ul>