Leetcode 526 Solution

This article provides solution to leetcode question 526 (beautiful-arrangement)
Categories:
Tags:
Access this page by simply typing in "lcs 526" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/beautiful-arrangement

Solution

class Solution:
    def countArrangement(self, n: int) -> int:
        bitmask = 0

        def dfs(i):
            nonlocal bitmask
            nonlocal n
            if i == n + 1:
                return 1

            ans = 0
            for j in range(1, n + 1):
                if bitmask & (1 << j):
                    continue

                if i % j != 0 and j % i != 0:
                    continue

                bitmask |= 1 << j
                ans += dfs(i + 1)
                bitmask ^= 1 << j

            return ans

        return dfs(1)