D
DevExCode

LeetCode 526: Beautiful Arrangement Solution

Master LeetCode problem 526 (Beautiful Arrangement), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

To solve this problem, we can use backtracking to try out all possible permutations of numbers from 1 to n, making sure that each number we place satisfies the given condition. We can keep track of used numbers and the current position we are trying to fill in the permutation. If at any point the condition is not satisfied, we backtrack and try a different number at that position.

Algorithm:

  1. Initialize a count variable to keep track of the number of beautiful arrangements.
  2. Implement a backtracking function that takes the current position and a set of used numbers as parameters.
  3. In the backtracking function:
    • Base case: If the current position is equal to n+1, increment the count by 1 as we have found a valid arrangement.
    • Iterate through numbers from 1 to n:
      • If the number is not used and either the number is divisible by the current position or the current position is divisible by the number, mark the number as used and recursively call the function with the next position.
      • After the recursive call, mark the number as unused to backtrack for other possible arrangements.
  4. Return the count of beautiful arrangements.

Time Complexity:

The time complexity of this backtracking solution is O(n!) as we are trying out all possible permutations.

Space Complexity:

The space complexity is O(n) due to the recursion stack and the set to keep track of used numbers. :

Solution Code

class Solution {
    public int countArrangement(int n) {
        return backtrack(1, new HashSet<>(), n);
    }

    private int backtrack(int pos, Set<Integer> used, int n) {
        if (pos == n + 1) {
            return 1;
        }

        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (!used.contains(i) && (i % pos == 0 || pos % i == 0)) {
                used.add(i);
                count += backtrack(pos + 1, used, n);
                used.remove(i);
            }
        }

        return count;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 526 (Beautiful Arrangement)?

This page provides optimized solutions for LeetCode problem 526 (Beautiful Arrangement) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 526 (Beautiful Arrangement)?

The time complexity for LeetCode 526 (Beautiful Arrangement) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 526 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 526 in Java, C++, or Python.

Back to LeetCode Solutions