526. Beautiful Arrangement
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:
- Initialize a count variable to keep track of the number of beautiful arrangements.
- Implement a backtracking function that takes the current position and a set of used numbers as parameters.
- 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.
- 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. :
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;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.