From e929408381a41cd9e6eef9bf73fdc08f25784856 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 18 Mar 2025 11:32:16 -0600 Subject: 526. beautiful arrangement --- beautiful_arrangement.c | 23 +++++++++++++++++++++++ beautiful_arrangement.py | 34 ++++++++++++++++++++++++++++++++++ 2 files changed, 57 insertions(+) create mode 100644 beautiful_arrangement.c create mode 100644 beautiful_arrangement.py 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)) -- cgit v1.2.3