Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement 
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation 
3.3.1.
Java
3.3.2.
C++ 
3.3.3.
Python
3.3.4.
Output
3.4.
Complexity Analysis
3.4.1.
Time Complexity
3.4.2.
Space Complexity
4.
Optimized Approach 
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation
4.3.1.
Java
4.3.2.
C++ 
4.3.3.
Python
4.3.4.
Output
4.4.
Complexity Analysis
4.4.1.
Time Complexity
4.4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What are the conditions stated for a permutation to be a beautiful arrangement?
5.2.
What is the permutation?
5.3.
What is the boolean array?
5.4.
What are the different approaches of solving beautiful arrangement problem?
5.5.
What is the best time complexity for solving a beautiful arrangement problem?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Beautiful Arrangement

Author Harsh Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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.

Introduction

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. 

Also read, Permutation of string

Problem Statement 

Problem statement

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:

conditions

Constraints 

  • N is a positive integer.
  • N is between 1 to 15.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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:

array

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:

case 1

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);
    }
}

C++ 

#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;
}

Python

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)

Output

output

Complexity Analysis

Time Complexity

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).

Read More - Time Complexity of Sorting Algorithms

Optimized Approach 

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:

First space


Now, let’s look at each pair independently. Starting with the first pair = [1] and [2,3].

first pair

Recursively check for 2nd pair.

second pair

The conditions for the third pair will be as follows - 

third pair

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);
    }
}

C++ 

#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;
}

Python

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)

Output

output

Complexity Analysis

Time Complexity

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).

Check out this problem - Longest Subarray With Sum K 

Frequently Asked Questions

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:

 

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSACompetitive ProgrammingJava Programming, and System Design, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.

If you think that this blog helped you, then share it with your friends!

All the best for your future endeavors, and Keep Coding.

Previous article
Stepping Numbers
Next article
Understanding Stock Span
Live masterclass