diff options
author | Jack Sangdahl <[email protected]> | 2025-03-18 11:32:16 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-18 11:32:16 -0600 |
commit | e929408381a41cd9e6eef9bf73fdc08f25784856 (patch) | |
tree | d7f9b6248f18b171eaf0a0bf93d1f50d8b1aff8d | |
parent | a1f80208dda2f142674ed9dc260063009e96dee1 (diff) | |
download | leetcode-e929408381a41cd9e6eef9bf73fdc08f25784856.tar.gz leetcode-e929408381a41cd9e6eef9bf73fdc08f25784856.zip |
526. beautiful arrangement
-rw-r--r-- | beautiful_arrangement.c | 23 | ||||
-rw-r--r-- | beautiful_arrangement.py | 34 |
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)) |