Beautiful Arrangement – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

• perm[i] is divisible by i.
• i is divisible by perm[i].

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

Example 1:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 15

C++ Beautiful Arrangement LeetCode Solution

class Solution {
public:
    bool seen[16] = {};
    int res = 0;
    int dfs(int n, int pos = 1) {
        if (pos > n) return res++;
        for (int i = 1; i <= n; i++) {
            if (!seen[i] && (i % pos == 0 || pos % i == 0)) {
                // marking i as seen
                seen[i] = true;
                dfs(n, pos + 1);
                // backtracking
                seen[i] = false;
            }
        }
        return res;
    }
    int countArrangement(int n) {
        if (n < 4) return n;
        return dfs(n);
    }
};

Java Beautiful Arrangement LeetCode Solution

 private int count = 0;
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void helper(int[] nums, int start) {
        if (start == 0) {
            count++;
            return;
        }
        for (int i = start; i > 0; i--) {
            swap(nums, start, i);
            if (nums[start] % start == 0 || start % nums[start] == 0) helper(nums, start-1);
            swap(nums,i, start);
        }
    }
    public int countArrangement(int N) {
        if (N == 0) return 0;
        int[] nums = new int[N+1];
        for (int i = 0; i <= N; i++) nums[i] = i;
        helper(nums, N);
        return count;
    }
 

Python 3 Beautiful Arrangement LeetCode Solution

def countArrangement(self, N):
    def count(i, X):
        if i > N:
            return 1
        return sum(count(i + 1, X - {x})
                   for x in X
                   if x % i == 0 or i % x == 0)
    return count(1, set(range(1, N + 1)))

Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264

Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195

Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140

Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96

Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66

Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40

Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31

Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21

Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16

Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9

Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7

Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4

Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3

Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1

Leave a comment below

Related posts:

Combination Sum II – LeetCode Solution Rotate Image – LeetCode Solution Plus One – LeetCode Solution Max Points on a Line – LeetCode Solution Single Number III – LeetCode Solution Island Perimeter – LeetCode Solution