Jobs

Interviews

Discussions

Beautiful Arrangement

Medium

Asked by:

51 views

Topics:

ArraysRecursionBit ManipulationDynamic Programming

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

Try coding it in LeetCode

Beautiful Arrangement

Medium

Asked by:

51 views

Topics:

ArraysRecursionBit ManipulationDynamic Programming

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`? What are the constraints on the size of `n`?
Are we only dealing with positive integers from 1 to `n`?
If no beautiful arrangement is possible, what should I return? Should I return an empty list or a specific error code?
Are we looking for the total count of beautiful arrangements or do we need to generate the actual arrangements?
In the case of multiple beautiful arrangements, is there any preference for which one I should return if I'm asked to return an actual arrangement and not just the count?

Brute Force Solution

Approach

The brute force approach to this problem is to simply try out every single possible arrangement of the numbers. We will check if each arrangement meets the 'beautiful' criteria. By trying every possibility, we guarantee we will find all valid arrangements.

Here's how the algorithm would work step-by-step:

Start by considering the first number and trying every possible choice from the available numbers.
Once you've chosen the first number, move on to the second position and again try all the remaining available numbers.
Continue this process, choosing a number for each position one at a time, until you've placed all the numbers.
After forming a complete arrangement, check if it is 'beautiful'. That means, check if each number at each position satisfies the condition involving divisibility or the reverse.
If the arrangement is indeed beautiful, count it.
Repeat this whole process of generating arrangements and checking them until you have tried every possible arrangement.
The final count of all the beautiful arrangements is the answer.

Code Implementation

def beautiful_arrangement_brute_force(number):
    count = 0
    numbers = list(range(1, number + 1))

    def backtrack(index, available_numbers):
        nonlocal count

        # If we've used all numbers,
        # check if arrangement is valid
        if index == number:
            count += 1
            return

        for current_number in available_numbers:

            # Create a new list of available
            # numbers for the next recursive step
            remaining_numbers = available_numbers[:]
            remaining_numbers.remove(current_number)

            # Check the beautiful arrangement condition
            # before continuing down the recursion
            if (current_number % (index + 1) == 0) or \
               ((index + 1) % current_number == 0):

                # Recursively build the arrangement
                backtrack(index + 1, remaining_numbers)

    # Start the backtracking with an index of 0
    # and all numbers available
    backtrack(0, numbers)
    return count

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach generates all possible permutations of the numbers from 1 to n. Generating all permutations takes O(n!) time because there are n! different arrangements. For each permutation, we need to check if it is a beautiful arrangement, which involves iterating through the n elements of the permutation. Thus, the overall time complexity is O(n * n!). However, since n! grows much faster than n, we can simplify the time complexity to O(n!).

Space Complexity

O(N) – The described brute force approach uses recursion to generate arrangements. In the worst case, the depth of the recursion can reach N, where N is the number of integers to arrange. Each recursive call creates a new stack frame, storing the current state of the arrangement being built. Therefore, the auxiliary space used by the recursion stack grows linearly with N, resulting in O(N) space complexity.

Optimal Solution

Approach

The goal is to count special ways to arrange numbers. Instead of checking every single arrangement, we use a smart, step-by-step strategy. This involves figuring out which numbers can fit together based on the given rule and counting the possibilities efficiently.

Here's how the algorithm would work step-by-step:

Start by placing the first number.
For each remaining position, consider only the numbers that satisfy the specified condition (either divisible by the position or the position is divisible by the number).
Keep track of how many ways you can successfully fill the rest of the positions given the choices you've made so far.
When you reach the end, you've found one valid arrangement, so increase your count.
By exploring only valid choices at each step, you avoid wasting time on arrangements that won't work.

Code Implementation

def beautiful_arrangement(number):    total_arrangements = 0
    available_numbers = list(range(1, number + 1))
    
    def count_arrangements(current_position, remaining_numbers):
        nonlocal total_arrangements

        # We found a valid arrangement
        if not remaining_numbers:
            total_arrangements += 1
            return

        # Iterate through the remaining numbers to find a suitable choice
        for index, number_to_place in enumerate(remaining_numbers):

            # Check divisibility condition. We only proceed if the
            # condition is met, backtracking otherwise.
            if (number_to_place % current_position == 0) or \
               (current_position % number_to_place == 0):
                # Create a new list excluding the selected number
                next_remaining_numbers = remaining_numbers[:index] + remaining_numbers[index+1:]

                # Recursively continue to the next position
                count_arrangements(current_position + 1, next_remaining_numbers)

    # Kick off the recursive process
    count_arrangements(1, available_numbers)
    
    return total_arrangements

Big(O) Analysis

Time Complexity

O(n!) – The algorithm explores possible permutations of numbers from 1 to n. In the worst case, we explore every possible arrangement. The number of possible arrangements is n factorial (n!). Therefore, the time complexity is O(n!). While the algorithm uses backtracking to prune invalid arrangements early, in the worst-case scenario where many arrangements are nearly valid, it still needs to explore a significant portion of the permutation space. The divisibility check within each recursive call contributes a smaller, constant factor, so it doesn't dominate the overall complexity.

Space Complexity

O(N) – The algorithm uses recursion to explore possible arrangements. In the worst-case scenario, where each number can be placed in many positions, the recursion depth can reach N, where N is the number of positions to fill. Each recursive call adds a new frame to the call stack, storing local variables and the return address. Therefore, the space used by the call stack grows linearly with N, resulting in O(N) auxiliary space.

Edge Cases

Case	How to Handle
n = 0	Return 0 or 1 (depending on the specific problem definition) if n is zero as there are no possible arrangements.
n = 1	Return 1 because there is one possible arrangement: [1].
n is a large number (scalability)	Be mindful of recursion depth, which can lead to stack overflow errors; memoization or dynamic programming can improve efficiency for larger n.
Inputs with only even or odd numbers for large n.	The recursive function may need to explore a large number of invalid states before discovering a solution; memoization can mitigate this.
Integer overflow for very large n in calculations.	Use appropriate data types (e.g., long) or modular arithmetic if intermediate results can exceed integer limits.
Cases where no valid solution exists (very rare, but theoretically possible)	Ensure the algorithm doesn't enter an infinite loop attempting to find a solution when none exists, and that it handles this gracefully.
Inputs where the initial permutation leads to early pruning	Consider strategies to explore more promising permutations early on, possibly through heuristic ordering.
Language specific stack overflow with deep recursion	Consider iterative solution or tail call optimization if supported, otherwise limit the depth of the recursion.

n = 0

How to Handle:

Return 0 or 1 (depending on the specific problem definition) if n is zero as there are no possible arrangements.

n = 1

How to Handle:

Return 1 because there is one possible arrangement: [1].

n is a large number (scalability)

How to Handle:

Be mindful of recursion depth, which can lead to stack overflow errors; memoization or dynamic programming can improve efficiency for larger n.

Inputs with only even or odd numbers for large n.

How to Handle:

The recursive function may need to explore a large number of invalid states before discovering a solution; memoization can mitigate this.

Integer overflow for very large n in calculations.

How to Handle:

Use appropriate data types (e.g., long) or modular arithmetic if intermediate results can exceed integer limits.

Cases where no valid solution exists (very rare, but theoretically possible)

How to Handle:

Ensure the algorithm doesn't enter an infinite loop attempting to find a solution when none exists, and that it handles this gracefully.

Inputs where the initial permutation leads to early pruning

How to Handle:

Consider strategies to explore more promising permutations early on, possibly through heuristic ordering.

Language specific stack overflow with deep recursion

How to Handle:

Consider iterative solution or tail call optimization if supported, otherwise limit the depth of the recursion.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of `n`? What are the constraints on the size of `n`?
Are we only dealing with positive integers from 1 to `n`?
If no beautiful arrangement is possible, what should I return? Should I return an empty list or a specific error code?
Are we looking for the total count of beautiful arrangements or do we need to generate the actual arrangements?
In the case of multiple beautiful arrangements, is there any preference for which one I should return if I'm asked to return an actual arrangement and not just the count?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the first number and trying every possible choice from the available numbers.
Once you've chosen the first number, move on to the second position and again try all the remaining available numbers.
Continue this process, choosing a number for each position one at a time, until you've placed all the numbers.
After forming a complete arrangement, check if it is 'beautiful'. That means, check if each number at each position satisfies the condition involving divisibility or the reverse.
If the arrangement is indeed beautiful, count it.
Repeat this whole process of generating arrangements and checking them until you have tried every possible arrangement.
The final count of all the beautiful arrangements is the answer.

Code Implementation

def beautiful_arrangement_brute_force(number):
    count = 0
    numbers = list(range(1, number + 1))

    def backtrack(index, available_numbers):
        nonlocal count

        # If we've used all numbers,
        # check if arrangement is valid
        if index == number:
            count += 1
            return

        for current_number in available_numbers:

            # Create a new list of available
            # numbers for the next recursive step
            remaining_numbers = available_numbers[:]
            remaining_numbers.remove(current_number)

            # Check the beautiful arrangement condition
            # before continuing down the recursion
            if (current_number % (index + 1) == 0) or \
               ((index + 1) % current_number == 0):

                # Recursively build the arrangement
                backtrack(index + 1, remaining_numbers)

    # Start the backtracking with an index of 0
    # and all numbers available
    backtrack(0, numbers)
    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by placing the first number.
For each remaining position, consider only the numbers that satisfy the specified condition (either divisible by the position or the position is divisible by the number).
Keep track of how many ways you can successfully fill the rest of the positions given the choices you've made so far.
When you reach the end, you've found one valid arrangement, so increase your count.
By exploring only valid choices at each step, you avoid wasting time on arrangements that won't work.

Code Implementation

def beautiful_arrangement(number):    total_arrangements = 0
    available_numbers = list(range(1, number + 1))
    
    def count_arrangements(current_position, remaining_numbers):
        nonlocal total_arrangements

        # We found a valid arrangement
        if not remaining_numbers:
            total_arrangements += 1
            return

        # Iterate through the remaining numbers to find a suitable choice
        for index, number_to_place in enumerate(remaining_numbers):

            # Check divisibility condition. We only proceed if the
            # condition is met, backtracking otherwise.
            if (number_to_place % current_position == 0) or \
               (current_position % number_to_place == 0):
                # Create a new list excluding the selected number
                next_remaining_numbers = remaining_numbers[:index] + remaining_numbers[index+1:]

                # Recursively continue to the next position
                count_arrangements(current_position + 1, next_remaining_numbers)

    # Kick off the recursive process
    count_arrangements(1, available_numbers)
    
    return total_arrangements

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return 0 or 1 (depending on the specific problem definition) if n is zero as there are no possible arrangements.
n = 1	Return 1 because there is one possible arrangement: [1].
n is a large number (scalability)	Be mindful of recursion depth, which can lead to stack overflow errors; memoization or dynamic programming can improve efficiency for larger n.
Inputs with only even or odd numbers for large n.	The recursive function may need to explore a large number of invalid states before discovering a solution; memoization can mitigate this.
Integer overflow for very large n in calculations.	Use appropriate data types (e.g., long) or modular arithmetic if intermediate results can exceed integer limits.
Cases where no valid solution exists (very rare, but theoretically possible)	Ensure the algorithm doesn't enter an infinite loop attempting to find a solution when none exists, and that it handles this gracefully.
Inputs where the initial permutation leads to early pruning	Consider strategies to explore more promising permutations early on, possibly through heuristic ordering.
Language specific stack overflow with deep recursion	Consider iterative solution or tail call optimization if supported, otherwise limit the depth of the recursion.

n = 0

How to Handle:

Return 0 or 1 (depending on the specific problem definition) if n is zero as there are no possible arrangements.

n = 1

How to Handle:

Return 1 because there is one possible arrangement: [1].

n is a large number (scalability)

How to Handle:

Be mindful of recursion depth, which can lead to stack overflow errors; memoization or dynamic programming can improve efficiency for larger n.

Inputs with only even or odd numbers for large n.

How to Handle:

The recursive function may need to explore a large number of invalid states before discovering a solution; memoization can mitigate this.

Integer overflow for very large n in calculations.

How to Handle:

Use appropriate data types (e.g., long) or modular arithmetic if intermediate results can exceed integer limits.

Cases where no valid solution exists (very rare, but theoretically possible)

How to Handle:

Ensure the algorithm doesn't enter an infinite loop attempting to find a solution when none exists, and that it handles this gracefully.

Inputs where the initial permutation leads to early pruning

How to Handle:

Consider strategies to explore more promising permutations early on, possibly through heuristic ordering.

Language specific stack overflow with deep recursion

How to Handle:

Consider iterative solution or tail call optimization if supported, otherwise limit the depth of the recursion.