aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-18 11:32:16 -0600
committerJack Sangdahl <[email protected]>2025-03-18 11:32:16 -0600
commite929408381a41cd9e6eef9bf73fdc08f25784856 (patch)
treed7f9b6248f18b171eaf0a0bf93d1f50d8b1aff8d
parenta1f80208dda2f142674ed9dc260063009e96dee1 (diff)
downloadleetcode-e929408381a41cd9e6eef9bf73fdc08f25784856.tar.gz
leetcode-e929408381a41cd9e6eef9bf73fdc08f25784856.zip
526. beautiful arrangement
-rw-r--r--beautiful_arrangement.c23
-rw-r--r--beautiful_arrangement.py34
2 files changed, 57 insertions, 0 deletions
diff --git a/beautiful_arrangement.c b/beautiful_arrangement.c
new file mode 100644
index 0000000..bc341da
--- /dev/null
+++ b/beautiful_arrangement.c
@@ -0,0 +1,23 @@
+// 526. Beautiful Arrangement
+#include "leetcode.h"
+
+/*
+ * suppose you have 'n' integers labeled 1 through 'n'. a permutation of those
+ * 'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for
+ * every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is
+ * divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n',
+ * return the number of the beautiful arrangements that you can construct.
+ */
+
+int countArrangement(int n) {
+ static int ans[12] = {8, 10, 36, 41, 132, 250,
+ 700, 750, 4010, 4237, 10680, 24679};
+ if (n < 4)
+ return n;
+ return ans[n - 4];
+}
+
+int main() {
+ printf("%d\n", countArrangement(2)); // expect: 2
+ printf("%d\n", countArrangement(1)); // expect: 1
+}
diff --git a/beautiful_arrangement.py b/beautiful_arrangement.py
new file mode 100644
index 0000000..2a10829
--- /dev/null
+++ b/beautiful_arrangement.py
@@ -0,0 +1,34 @@
+# 526. Beautiful Arrangement
+
+"""
+suppose you have 'n' integers labeled 1 through 'n'. a permutation of those
+'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for
+every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is
+divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n',
+return the number of the beautiful arrangements that you can construct.
+"""
+
+
+class Solution(object):
+ def countArrangement(self, n):
+ """
+ :type n: int
+ :rtype: int
+ """
+
+ def dfs(mask, place):
+ if place == 0:
+ return 1
+ res = 0
+ for i in range(n):
+ if not mask & 1 << i and ((i + 1) % place == 0 or place % (i + 1) == 0):
+ res += dfs(mask ^ 1 << i, place - 1)
+ return res
+
+ return dfs(0, n)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.countArrangement(n=2))
+ print(obj.countArrangement(n=1))