algoadvance

Leetcode 526. Beautiful Arrangement

Problem Statement

You are given an integer n. A permutation of the first n positive integers is considered beautiful if for every i (1 ≤ i ≤ n), one of the following is true:

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

Given an integer n, return the number of the beautiful arrangements that you can construct.

Clarifying Questions

  1. What is the range of n?
    • n will be an integer such that 1 ≤ n ≤ 15.
  2. What should the function return if n is 1?
    • The result should be 1 since there is only one permutation of {1} which is trivially beautiful.
  3. Is there any specific input format?
    • The input will be a single integer n.

Strategy

To solve this problem, we will use a backtracking approach:

  1. Generate permutations of the first n positive integers.
  2. For each permutation, check if it satisfies the conditions of a beautiful arrangement.
  3. Count all the permutations that are beautiful arrangements.

Detailed Steps:

  1. Generate Permutations: Use backtracking to generate permutations of the list [1, 2, ..., n].
  2. Check Permutation: For each permutation, check if each element at position i satisfies the beautiful arrangement conditions, i.e., i is divisible by the element at the i-th position or the element at the i-th position is divisible by i.
  3. Count Beautiful Arrangements: Maintain a count of all valid (beautiful) permutations.

Time Complexity

Now, let’s implement the solution.

Code

#include <vector>

class Solution {
public:
    int countArrangement(int n) {
        if (n < 1) return 0;
        
        std::vector<bool> visited(n + 1, false);
        return countArrangementHelper(n, 1, visited);
    }
    
private:
    int countArrangementHelper(int n, int pos, std::vector<bool>& visited) {
        if (pos > n) {
            return 1;
        }
        
        int count = 0;
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] && (i % pos == 0 || pos % i == 0)) {
                visited[i] = true;
                count += countArrangementHelper(n, pos + 1, visited);
                visited[i] = false;
            }
        }
        
        return count;
    }
};

Explanation:

  1. The function countArrangement initializes a visited array to keep track of which numbers have been used.
  2. It calls the helper function countArrangementHelper starting from position 1.
  3. The helper function recursively tries to place each number from 1 to n in the current position (pos), ensuring the beautiful arrangement condition.
  4. Once pos exceeds n, it means a valid arrangement has been found, and it returns 1.
  5. If a valid number is placed at position pos, the function recurses for the next position.
  6. The visited array ensures that each number is used only once per arrangement.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI