Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
In this article, we will discuss a problem named Beautiful Arrangements. This blog will discuss the various approaches to solving this problem and each approach's time and space complexities. Before jumping into the problem of getting the number of beautiful arrangements, let's first understand what a beautiful arrangement is.
A beautiful arrangement is the permutations of 'N' integers when either of the following statements is true:
Permutation at arr[i] is divisible by ‘i’
‘i’ is divisible by permutation at arr[i], where ‘i’ refers to a numeric index
Example:
Input: N = 3
The number of beautiful arrangements are = 3
Explanation:
The two beautiful arrangements can be [1, 2,3], [2, 1, 3], and [3, 2, 1], as they satisfy at least one condition given for a beautiful arrangement.
You are given an integer N, and we have to create an array using integers from 1 to N. Our task is to create an array of beautiful arrangements of these numbers from 1 to N. We need to print the number of possible beautiful arrangements.
We define a beautiful arrangement as, for every ‘i’(1 <= i <= N), either of the below-mentioned condition is true:
Constraints
N is a positive integer.
N is between 1 to 15.
Brute Force Approach
A brute Force Solution considers every permutation of the elements from 1 to 'N'. Then, we have to iterate over all the elements of every permutation generated, and then we need to check the required given two divisibility conditions. Let's first discuss the algorithm and then the implementation for the same.
Algorithm
Step 1: Create a function 'getResult()' that will accept one parameter, i.e., 'N'- the upper bound of the elements we need to consider.
Step 2: Create an array 'arr' and make an iteration from 1 to 'N' using a variable 'i', and assign 'i' to each of its respective 'i - 1' elements of the 'arr'.
Step 3: Make a function call to the 'helper' function passing two parameters, the first will be the 'arr', and the second will be the current index.
Step 4: In the 'helper' function, make an edge condition that if the value of 'index' is equal to the size of the 'arr', then make an iteration using the 'for' loop with variable 'i' from 1 to the length of the 'arr.
Step 5: In this 'for' loop, if any element doesn't satisfy any of the two conditions, then break the for loop, and if the value of i is equal to the size of 'arr' + 1, then increment the count.
Step 6: Make another iteration using for loop from 'i' = 1 to 'i' < size of the 'arr', and in this call, the swap function will swap the current element with every other element in the array on the right side of the element.
Step 7: Make another 'helper' call with the index of the next element in the array.
Step 8. Now, reverse the swapping which was done in the current function call.
Dry Run
Let's understand the algorithm using an example. For example - the value of N = 3. As it is a brute-force approach, we will look at every possible arrangement. So we will create an array 'arr' of size N and assign the number 1 to N. Our array will look like this:
Now we will call the helper function passing this array and index value = 0 (for starting with the first number). This function iterates from the index value to the array size, i.e., from 0 to 3. And, in each iteration, we will swap arr[i] with arr[index].
For i=0, the possible arrangements are as follows:
So, the value of the count is now = 3. Increment the value of i = 1. For i = 1, the operations are as follows:
Swap arr[1] with arr[2]
Arrangement = [1,3,2]
Check for arr[0] : 1%1 == 0
Check for arr[1] : 3%2 not equal to 0 and 2%3 not equal to 0
As for arr[1], none of the conditions is true, for this is not a valid arrangement.
Now increment the value of i = 2, as 'i' == array size, so the loop terminates. Return the value of count = 3.
Implementation
Java
public class Main {
int count = 0;
public int getResult(int N) {
int[] arr = new int[N];
// Assigning 1 to N value
for (int i = 1; i <= N; i++)
arr[i - 1] = i;
helper(arr, 0);
return count;
}
public void helper(int[] arr, int index) {
// Edge case
if (index == arr.length - 1) {
int i;
for (i = 1; i <= arr.length; i++) {
// Not satisfying at least one condition
if (arr[i - 1] % i != 0 && i % arr[i - 1] != 0)
break;
}
if (i == arr.length + 1)
count++;
}
for (int i = index; i < arr.length; i++) {
swap(arr, i, index);
helper(arr, index + 1);
swap(arr, i, index);
}
}
// Create Swap Function
public void swap(int[] arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public static void main(String[] args) {
Main solution = new Main();
int res = solution.getResult(5);
System.out.println("Total Number of Beautiful arrangements are : " + res);
int res2 = solution.getResult(8);
System.out.println("Total Number of Beautiful arrangements are : " + res2);
}
}
You can also try this code with Online Java Compiler
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getResult(int N) {
vector<int>arr(N);
// Assigning 1 to N value
for (int i = 1; i <= N; i++)
arr[i - 1] = i;
int count=0;
helper(arr, count, 0);
return count;
}
void helper(vector<int>&arr,int &count, int index) {
// Edge case
if(index==arr.size())
count++;
for(int i=index;i<arr.size();i++){
swap(arr[i],arr[index]);
// Satisfying at least one condition
if(arr[index]%(index+1)==0 || (index+1)%arr[index]==0)
helper(arr, count, index+1);
swap(arr[i],arr[index]);
}
}
};
int main() {
Solution solution;
int res = solution.getResult(5);
cout<<"Total Number of Beautiful arrangements are : "<< res << endl;
int res2 = solution.getResult(8);
cout<<"Total Number of Beautiful arrangements are : "<< res2 << endl;
return 0;
}
You can also try this code with Online C++ Compiler
class Solution:
def getResult(self,N):
count = 0
arr = [i for i in range(1, N + 1)]
self.count = 0
self.helper(arr, 0)
return self.count
def helper(self, arr, index):
# Edge case
if index == len(arr):
self.count += 1\
for i in range(index, len(arr)):
arr[i], arr[index] = arr[index], arr[i]
# Satisfying at least one condition
if arr[index]%(index+1) == 0 or (index+1)%arr[index] == 0:
self.helper(arr, index+1)
arr[i], arr[index] = arr[index], arr[i]
solution = Solution()
res = solution.getResult(5)
print("Total Number of Beautiful arrangements are : ",res)
res2 = solution.getResult(8)
print("Total Number of Beautiful arrangements are : ",res2)
You can also try this code with Online Python Compiler
The time complexity required is - O(N!). In the call to 'getResult()', we generate N! Permutations of array length 'N'. Therefore, the overall time complexity will be O(N!).
Space Complexity
The space complexity required is - O(1). As we generate N! Permutations, the recursion tree can go upto 'N'. Therefore the overall space complexity will be O(N).
To optimize this beautiful arrangement problem, we'll try to create all the possible combinations of the numbers ranging from 1 to 'N'. We can try to fix a particular number at a particular position, and then we can check for the stated conditions of that number at that particular position. Along with this, we need to keep a record of the number which has been previously considered to avoid repeated computations of the same number. Also, we need to consider that if a particular number doesn't satisfy any of the given conditions, we don't need to check the rest of the combinations.
In this approach, We used an array named ‘vis’ f size ‘N’ to record the particular number being visited once or not.
Algorithm
Step 1. In the function call to the 'getResult()' function, create a boolean array named 'vis' which will be of size 'N + 1'.
Step 2. Make a call to the 'helper' function by passing three parameters which are 'N', 1 , and the boolean array 'vis'.
Step 3. In the 'helper' function, create an edge case, in which if the position received is greater than 'N', then increment the 'count' variable.
Step 4. Now, make an iteration using 'i' from 1 to 'N', in which if the boolean value at ith index is false and if it satisfies the stated condition, then change that boolean value to true and call the 'helper' function but this time pass the next position, and then after this recursive call, change that boolean value to false.
Step 5. Return the 'count'.
Dry Run
Let's understand the algorithm using a dry run. As an example, let's take the value of N = 3. As in the optimized approach, we first select one element and then look at the arrangements for other spaces. So, the first space will be as follows:
Now, let’s look at each pair independently. Starting with the first pair = [1] and [2,3].
Recursively check for 2nd pair.
The conditions for the third pair will be as follows -
So, for N = 3, the Number of beautiful arrangements are 3. These are - [1,2,3], [2,1,3], and [3,2,1].
Implementation
Java
public class Main
{
int count = 0;
// Create get Result function
public int getResult(int N) {
// Create boolean array
boolean[] vis = new boolean[N + 1];
helper(N, 1, vis);
return count;
}
//Create helper function
public void helper(int N, int pos, boolean[] vis) {
// Edge case
if (pos > N)
count++;
for (int i = 1; i <= N; i++) {
// Not satisfying at least one condition
if (!vis[i] && (pos % i == 0 || i % pos == 0)){
vis[i] = true;
helper(N, pos + 1, vis);
vis[i] = false;
}
}
}
public static void main(String[] args) {
Main solution = new Main();
int res = solution.getResult(5);
System.out.println("Total Number of Beautiful arrangements are : " + res);
int res2 = solution.getResult(8);
System.out.println("Total Number of Beautiful arrangements are : " + res2);
}
}
You can also try this code with Online Java Compiler
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
//Create get Result function
int getResult(int N) {
//Create boolean array
vector<bool> vis(N+1, 0);
int count = 0;
helper(N, 1, vis, count);
return count;
}
// Create helper function
void helper(int N, int pos, vector<bool> &vis, int &count) {
// Edge case
if(pos > N)
count++;
for(int i = 1; i <= N; i++) {
// Not satisfying at least one condition
if(vis[i] == false && (pos % i == 0 || i % pos == 0)) {
vis[i] = true;
helper(N, pos + 1, vis, count);
vis[i] = false;
}
}
}
};
int main(){
Solution solution;
int res = solution.getResult(5);
cout<<"Total Number of Beautiful arrangements are : "<< res << endl;
int res2 = solution.getResult(8);
cout<<"Total Number of Beautiful arrangements are : "<< res2 << endl;
return 0;
}
You can also try this code with Online C++ Compiler
class Solution:
# Create get result fucntion
def getResult(self, N: int) -> int:
# Create boolean array
vis = [False for _ in range(N+1)]
self.count = 0
self.helper(N,1,vis)
return self.count
# Create helper function
def helper(self, N, index, vis):
# Edge case
if index > N:
self.count += 1
for i in range(1, N+1):
# Not satisfying at least one condition
if not vis[i] and (index % i == 0 or i % index == 0):
vis[i] = True
self.helper(N, index+1, vis)
vis[i] = False
solution = Solution()
res = solution.getResult(5)
print("Total Number of Beautiful arrangements are : ",res)
res2 = solution.getResult(8)
print("Total Number of Beautiful arrangements are : ",res2)
You can also try this code with Online Python Compiler
The time complexity required is O(K), where ‘K’ refers to the total number of valid permutations, as we can see, we are proceeding forward only if it is a valid permutation. Therefore, the overall time complexity will be O(K).
Space Complexity
As we are using the ‘vis’ array, which will be of size ‘N’. Therefore the overall space complexity is O(N).
What are the conditions stated for a permutation to be a beautiful arrangement?
There are two conditions, which are as follows:- permutation at arr[i] is divisible by ‘i’ and ‘I’ is divisible by permutation at arr[i].
What is the permutation?
A permutation of a number refers to the state of its one of the combinations.
What is the boolean array?
The Boolean array is the array in which the array elements can either contain the true or false value.
What are the different approaches of solving beautiful arrangement problem?
Beautiful arrangement problem can be solved using dynamic programming, bit-manipulation, backtracking, and bitmasking.
What is the best time complexity for solving a beautiful arrangement problem?
The time complexity required is O(K), where ‘K’ refers to the total number of valid permutations.
Conclusion
In this article, we discussed the What is Beautiful Arrangement problem, discussed the various approaches to solving this problem programmatically, and the time and space complexities. We find out how to use extra space and drastically reduce the time complexity.
If you want to learn more about such problems, visit the given links below: