526. Beautiful Arrangement #

Problem #

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

1. The number at the i position is divisible by i.th
2. i is divisible by the number at the i position.th

Now given N, how many beautiful arrangements can you construct?

Example 1:

Input: 2
Output: 2
Explanation: 

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

Note:

1. N is a positive integer and will not exceed 15.

Problem Summary #

Suppose there are N integers from 1 to N. If an array can be successfully constructed from these N numbers such that the ith position (1 <= i <= N) of the array satisfies one of the following two conditions, we call this array a beautiful arrangement. Conditions:

• The number at the ith position can be divided by i
• i can be divided by the number at the ith position

Now given an integer N, how many beautiful arrangements can be constructed?

Solution Approach #

• This problem is an enhanced version of Problem 46. Since the numbers in the array given in this problem are all distinct, it can be solved as Problem 46.
• The extra condition in this problem compared to Problem 46 is that the number must be divisible by its corresponding index + 1, or index + 1 must be divisible by the number corresponding to that index. Just add this pruning condition during the DFS backtracking process.
• The current approach is not optimal in time complexity, roughly only faster than 33.3%.

Code #

package leetcode

// Solution 1: brute-force lookup table
func countArrangement1(N int) int {
	res := []int{0, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812}
	return res[N]
}

// Solution 2: DFS backtracking
func countArrangement(N int) int {
	if N == 0 {
		return 0
	}
	nums, used, p, res := make([]int, N), make([]bool, N), []int{}, [][]int{}
	for i := range nums {
		nums[i] = i + 1
	}
	generatePermutation526(nums, 0, p, &res, &used)
	return len(res)
}

func generatePermutation526(nums []int, index int, p []int, res *[][]int, used *[]bool) {
	if index == len(nums) {
		temp := make([]int, len(p))
		copy(temp, p)
		*res = append(*res, temp)
		return
	}
	for i := 0; i < len(nums); i++ {
		if !(*used)[i] {
			if !(checkDivisible(nums[i], len(p)+1) || checkDivisible(len(p)+1, nums[i])) { // key pruning condition
				continue
			}
			(*used)[i] = true
			p = append(p, nums[i])
			generatePermutation526(nums, index+1, p, res, used)
			p = p[:len(p)-1]
			(*used)[i] = false
		}
	}
	return
}

func checkDivisible(num, d int) bool {
	tmp := num / d
	if int(tmp)*int(d) == num {
		return true
	}
	return false
}