diff options
Diffstat (limited to 'beautiful_arrangement.py')
-rw-r--r-- | beautiful_arrangement.py | 34 |
1 files changed, 34 insertions, 0 deletions
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)) |