Possible Beautiful Arrangements of given numbers

Consider you are given with a number N and you have to find the maximum possible number(just the count not the actual arrangements) of beautiful arrangements possible using numbers 1-N(i.e. 1,2,3, N-1, N). Now the question arises that what is a beautiful arrangement.

A particular arrangement of numbers is called a beautiful arrangement if any of the following is true:

1. The number present at the index i is divisible by i. i.e. (a[i]/i = Integer) OR
2. i is divisible by the number present at the index i. i.e. (i/a[i] = Integer)

Constraints –  1 < N < 20

Sample Input – 2
Sample Output – 2

Explanation
The number of possible beautiful arrangements for N=2 will be:
1 2
2 1

1. Consider the arrangement [1, 2] then:
   • number present at 1st position (i = 1) is 1, and 1 is divisible by i.
   • number present at 2nd position (i = 2) is 2, and 2 is divisible by i.
2. Consider the arrangement [2, 1] then:
   • number present at 1st position (i = 1) is 2, and 2 is divisible by i.
   • number present at 2nd position (i = 2) is 1, and i is divisible by 1.

Beautiful Arrangements Implementation

Now let’s do the coding part –

 package codingeek;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BeautifulArrangement {

    static int count;

    public static void main(String[] args) {
        System.out.println("Enter number (1-20) ");
        final Scanner sc = new Scanner(System.in);
        final int number = sc.nextInt();
        final List<Integer> availableNumbers = new ArrayList<>();
        for (int i = 1; i <= number; i++) {
            availableNumbers.add(i);
        }
        if (number >= 1) {
            findArrangement(1, availableNumbers, number);
            System.out.println("Possible number of arrangements - " + count);
        } else {
            System.out.println("Possible number of arrangements - " + 0);
        }
    }

    public static void findArrangement(final int index, final List<Integer> availableNumbers, final int number) {
        for (int i = 0; i < availableNumbers.size(); i++) {
            if (availableNumbers.get(i) % index == 0 || index % availableNumbers.get(i) == 0) {

            	final List<Integer> remainingNumbers = new ArrayList<>();
                remainingNumbers.addAll(availableNumbers);
                remainingNumbers.remove(availableNumbers.get(i));
                if (index < number) {
                    findArrangement(index + 1, remainingNumbers, number);
                } else {
                    count++;
                }
            }
        }
    }
}
 

Output:-
Enter number (1-20) - 8
Possible number of arrangements - 132

Now lets understand how this code works-

1. User enters the input number, lets’s say N.
2. An Arraylist of elements(1-N) is created and passed to the method findArrangement which recursively finds the possible number of arrangements by selecting one element for the current index that fulfills the criterion(Line 29). Then we create a new list which is missing the element that we have already fixed for the current index(Line 31-33) and passes the remaining list to the function for next call which then finds a suitable match for the next index location and with the remaining list(Line 35).
3. We increase the counter if we find suitable match for all the indexes(Line 37).
4. At the end the value of counter is the possible number of arrangements that are possible.

Guys, I know that we can create a much faster version of this program by keeping a memory map of parsed values but I left that work for you. Do create a new solution and I will include that solution in the post.

So that all for this post guys and do not forget to share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.

Keep Learning… Happy Learning.. 🙂

Recommended -