algoadvance

Leetcode 526. Beautiful Arrangement

Problem Statement

The problem is defined as follows:

Suppose you have n integers from 1 to n. We define a “beautiful arrangement” as an arrangement where for every i-th position 1 <= i <= n, either of the following is true:

• The number at the i-th position is divisible by i.
• i is divisible by the number at the i-th position.

Given an integer n, return the count of the beautiful arrangements that you can form.

Clarifying Questions

1. Input Constraints:
   • What is the range of n?
   • Can n be negative or zero?

   Response: Assume n is a positive integer and 1 <= n <= 15.

2. Output:
   • Is the output just the count of beautiful arrangements for given n?

   Response: Yes, the output should be the count of beautiful arrangements.

Strategy

To solve this problem, we can use backtracking to generate all possible permutations of the integers from 1 to n and count the permutations that satisfy the problem’s conditions.

Steps:

1. Backtracking Approach:
   • Use a boolean array to keep track of the visited numbers.
   • Recursively try placing each number 1 to n in positions 1 to n.
   • At each step, check if the current number can be placed in the current position based on the given conditions.
   • If the conditions are satisfied, recursively place the next number.
   • If all numbers are placed satisfying the conditions, increment the count of beautiful arrangements.
2. Termination Condition:
   • When we’ve placed all numbers successfully, increment the result count.
3. Optimization:
   • Since we only care about valid arrangements, we can prune branches early where it is impossible to place a number.

Code

Here is the Java code implementing the above strategy:

public class Solution {
    
    private int count = 0;
    
    public int countArrangement(int n) {
        boolean[] visited = new boolean[n + 1];
        backtrack(1, n, visited);
        return count;
    }
    
    private void backtrack(int position, int n, boolean[] visited) {
        if (position > n) {
            count++;
            return;
        }
        
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (i % position == 0 || position % i == 0)) {
                visited[i] = true;
                backtrack(position + 1, n, visited);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.countArrangement(2)); // Output: 2
    }
}

Time Complexity

• Time Complexity:
  • The algorithm will explore all the permutations of n numbers. In the worst case, this is O(n!) where n is the number of integers.
  • Each permutation needs to be checked whether it is a beautiful arrangement which takes O(n) time. Hence the overall time complexity is O(n! * n) for large n.
• Space Complexity:
  • The space complexity is mainly due to the recursion stack and the visited array.
  • The recursion stack can go as deep as n and the visited array takes O(n) space.
  • Therefore, the space complexity is O(n).

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?