LC-0526 Medium LeetCode

526. Beautiful Arrangement

Array Dynamic Programming Backtracking Bit Manipulation Bitmask

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 64% Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(n!)
# Space: O(n)


class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        def countArrangementHelper(n, arr):
            if n <= 0:
                return 1
            count = 0
            for i in xrange(n):
                if arr[i] % n == 0 or n % arr[i] == 0:
                    arr[i], arr[n-1] = arr[n-1], arr[i]
                    count += countArrangementHelper(n - 1, arr)
                    arr[i], arr[n-1] = arr[n-1], arr[i]
            return count

        return countArrangementHelper(N, range(1, N+1))

Solution from kamyu104/LeetCode-Solutions · MIT