leetcode/Python/beautiful-arrangement.py at master · Ollub/leetcode · GitHub

23 lines (19 loc) · 615 Bytes

# 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))

Expand file tree