Jobs

Interviews

Discussions

Number of Self-Divisible Permutations

Medium

Asked by:

59 views

Topics:

Dynamic ProgrammingBit Manipulation

Given an integer n, find the number of permutations of {1, 2, ..., n} such that for every i (1 <= i <= n), i is divisible by perm[i] or perm[i] is divisible by i.

Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 2
Output: 2
Explanation: 
The permutation [1,2] means that for every i (1 <= i <= 2):
- perm[1] = 1, 1 is divisible by i (1)
- perm[2] = 2, 2 is divisible by i (2)
The permutation [2,1] means that for every i (1 <= i <= 2):
- perm[1] = 2, 2 is divisible by i (1)
- perm[2] = 1, i (2) is divisible by perm[2] (1)

Example 2:

Input: n = 3
Output: 8

Constraints:

1 <= n <= 15

Try coding it in LeetCode

Number of Self-Divisible Permutations

Medium

Asked by:

59 views

Topics:

Dynamic ProgrammingBit Manipulation

Given an integer n, find the number of permutations of {1, 2, ..., n} such that for every i (1 <= i <= n), i is divisible by perm[i] or perm[i] is divisible by i.

Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 2
Output: 2
Explanation: 
The permutation [1,2] means that for every i (1 <= i <= 2):
- perm[1] = 1, 1 is divisible by i (1)
- perm[2] = 2, 2 is divisible by i (2)
The permutation [2,1] means that for every i (1 <= i <= 2):
- perm[1] = 2, 2 is divisible by i (1)
- perm[2] = 1, i (2) is divisible by perm[2] (1)

Example 2:

Input: n = 3
Output: 8

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 possible value of 'n'? Are there any constraints on the input size?
For the condition of self-divisibility, if a number at index i is 0, can i also be 0?
Are we only considering positive integers from 1 to n, or should I handle other cases, such as n being zero or negative?
If no self-divisible permutation exists for a given 'n', what should the function return?
Are we looking for distinct permutations only, or can permutations with the same numbers at the same positions be counted multiple times if generated through different calculation paths?

Brute Force Solution

Approach

The brute force way is to try every possible order of the numbers and see if it works. This means making all the different arrangements and checking each one to see if it fits our rule.

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

First, list out all the possible ways to arrange the numbers.
For each arrangement, check if every number is divisible by its position in the arrangement.
If a number is not divisible by its position, then that arrangement is not a valid solution.
Count the number of arrangements that satisfy the divisibility rule for every position.
The final count is the number of self-divisible permutations.

Code Implementation

def number_of_self_divisible_permutations(numbers):
    import itertools
    number_of_valid_permutations = 0
    all_permutations = list(itertools.permutations(numbers))

    for permutation in all_permutations:
        is_self_divisible = True

        # Check each number to see if it's self-divisible
        for index, number in enumerate(permutation):
            position = index + 1

            #If a number at any position is 0, skip since it will cause division by zero.
            if number == 0:
                is_self_divisible = False
                break

            # Check if the number divides evenly into its position.
            if position % number != 0:
                is_self_divisible = False
                break

        # Increment the count if the permutation is self-divisible.
        if is_self_divisible:
            number_of_valid_permutations += 1

    return number_of_valid_permutations

Big(O) Analysis

Time Complexity

O(n * n!) – The algorithm generates all possible permutations of the input array of size n. Generating all permutations takes O(n!) time. For each permutation, the algorithm iterates through the array of size n to check if the element at each index is divisible by the index + 1. Therefore, the time complexity is O(n * n!).

Space Complexity

O(N) – The brute force approach generates all possible permutations. To store a single permutation, an auxiliary array of size N is required, where N is the number of elements to permute. The recursion stack depth can reach up to N calls deep while generating these permutations. Therefore, the space complexity is determined by the size of a single permutation and the depth of the recursion stack, resulting in O(N).

Optimal Solution

Approach

To efficiently count self-divisible permutations, we'll use a technique called dynamic programming along with bit manipulation. Instead of exhaustively generating every permutation, we'll build up solutions incrementally, remembering previously computed results to avoid redundant calculations. This approach leverages bit manipulation to represent which numbers have already been placed in the permutation, making the entire process very fast.

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

We'll use a 'memory' to store intermediate results. Think of it as a lookup table that remembers how many partial permutations are self-divisible up to a certain point.
We'll also use 'bits' to keep track of which numbers have already been used in the permutation. Each bit represents whether a number has been placed or not.
Start with an empty permutation (no numbers placed yet).
Consider adding one number at a time to the permutation.
Before adding a number, check if it divides evenly by its position in the permutation (position 1, position 2, etc.). If it doesn't, don't add it – it can't be part of a self-divisible permutation.
If the number *does* divide evenly by its position, check if that number has already been used. If so, skip it.
If the number divides evenly and hasn't been used, add it to the permutation.
Update our 'memory' to record that we've extended a self-divisible partial permutation.
Repeat steps 4-8 until the permutation is complete (all numbers placed).
The value in our 'memory' after completing the full permutation will represent the total number of self-divisible permutations.

Code Implementation

def number_of_self_divisible_permutations(number):
    numbers = list(range(1, number + 1))
    count = 0
    memo = {}

    def permute(index, remaining_numbers):
        nonlocal count

        if index == number:
            count += 1
            return

        # Use tuple of remaining nums as key for memoization
        remaining_numbers_tuple = tuple(remaining_numbers)
        if (index, remaining_numbers_tuple) in memo:
            return memo[(index, remaining_numbers_tuple)]

        temp_count = 0
        for current_number in remaining_numbers:
            # Check divisibility before proceeding to prevent unnecessary computation
            if current_number % (index + 1) == 0:
                remaining_numbers_copy = remaining_numbers[:]
                remaining_numbers_copy.remove(current_number)
                permute(index + 1, remaining_numbers_copy)

        memo[(index, remaining_numbers_tuple)] = temp_count
        return temp_count

    permute(0, numbers)

    return count

Big(O) Analysis

Time Complexity

O(n * 2^n) – The algorithm uses dynamic programming with bit manipulation. The state of the DP is represented by a mask of used numbers (of size n), which means there are 2^n possible states. For each state, we iterate through each of the n numbers to check if it can be added to the current permutation. Therefore, the total time complexity is proportional to n multiplied by the number of states, leading to O(n * 2^n).

Space Complexity

O(N * 2^N) – The algorithm utilizes dynamic programming with bit manipulation. The 'memory' stores intermediate results, representing the number of self-divisible partial permutations. This 'memory' can be implemented as a 2D array or hash map. One dimension represents the position in the permutation (up to N), and the other represents the 'bits' which track used numbers, needing 2^N possibilities, where N is the number of integers. Therefore, the space complexity is O(N * 2^N).

Edge Cases

Case	How to Handle
n = 0	Since the problem specifies digits from 1 to n, if n is 0, there are no digits to permute, so the result should be 0.
n = 1	For n=1, the only permutation is [1], and 1 is divisible by 1, so the count is 1.
n = 2	For n=2, the permutations are [1, 2] and [2, 1]. 1 is divisible by 1 and 2 is divisible by 2 for [1,2], and 2 is divisible by 1 and 1 is not divisible by 2 for [2,1], so return 1.
Large n (e.g., n = 15)	The solution's time complexity should be carefully considered, as the number of permutations grows factorially, and memoization is critical.
n is a negative number	The problem statement defines n as an integer representing the range 1 to n, so negative values are invalid and return 0.
Input where no self-divisible permutations exist	The algorithm should correctly return 0 when no permutation satisfies the condition, such as a case where i isn't always divisible by the number at the ith position.
Integer Overflow	The count of permutations can grow very quickly, so using an appropriate data type (e.g., long in Java) to store the count is necessary to prevent integer overflow.
Recursion Depth Limits	For larger values of 'n' recursive solutions might hit the stack size limit. Consider iterative DFS with explicit stack or memoization to avoid exceeding recursion depth limits.

n = 0

How to Handle:

Since the problem specifies digits from 1 to n, if n is 0, there are no digits to permute, so the result should be 0.

n = 1

How to Handle:

For n=1, the only permutation is [1], and 1 is divisible by 1, so the count is 1.

n = 2

How to Handle:

For n=2, the permutations are [1, 2] and [2, 1]. 1 is divisible by 1 and 2 is divisible by 2 for [1,2], and 2 is divisible by 1 and 1 is not divisible by 2 for [2,1], so return 1.

Large n (e.g., n = 15)

How to Handle:

The solution's time complexity should be carefully considered, as the number of permutations grows factorially, and memoization is critical.

n is a negative number

How to Handle:

The problem statement defines n as an integer representing the range 1 to n, so negative values are invalid and return 0.

Input where no self-divisible permutations exist

How to Handle:

The algorithm should correctly return 0 when no permutation satisfies the condition, such as a case where i isn't always divisible by the number at the ith position.

Integer Overflow

How to Handle:

The count of permutations can grow very quickly, so using an appropriate data type (e.g., long in Java) to store the count is necessary to prevent integer overflow.

Recursion Depth Limits

How to Handle:

For larger values of 'n' recursive solutions might hit the stack size limit. Consider iterative DFS with explicit stack or memoization to avoid exceeding recursion depth limits.

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 possible value of 'n'? Are there any constraints on the input size?
For the condition of self-divisibility, if a number at index i is 0, can i also be 0?
Are we only considering positive integers from 1 to n, or should I handle other cases, such as n being zero or negative?
If no self-divisible permutation exists for a given 'n', what should the function return?
Are we looking for distinct permutations only, or can permutations with the same numbers at the same positions be counted multiple times if generated through different calculation paths?

Brute Force Solution

Approach

The brute force way is to try every possible order of the numbers and see if it works. This means making all the different arrangements and checking each one to see if it fits our rule.

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

First, list out all the possible ways to arrange the numbers.
For each arrangement, check if every number is divisible by its position in the arrangement.
If a number is not divisible by its position, then that arrangement is not a valid solution.
Count the number of arrangements that satisfy the divisibility rule for every position.
The final count is the number of self-divisible permutations.

Code Implementation

def number_of_self_divisible_permutations(numbers):
    import itertools
    number_of_valid_permutations = 0
    all_permutations = list(itertools.permutations(numbers))

    for permutation in all_permutations:
        is_self_divisible = True

        # Check each number to see if it's self-divisible
        for index, number in enumerate(permutation):
            position = index + 1

            #If a number at any position is 0, skip since it will cause division by zero.
            if number == 0:
                is_self_divisible = False
                break

            # Check if the number divides evenly into its position.
            if position % number != 0:
                is_self_divisible = False
                break

        # Increment the count if the permutation is self-divisible.
        if is_self_divisible:
            number_of_valid_permutations += 1

    return number_of_valid_permutations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

We'll use a 'memory' to store intermediate results. Think of it as a lookup table that remembers how many partial permutations are self-divisible up to a certain point.
We'll also use 'bits' to keep track of which numbers have already been used in the permutation. Each bit represents whether a number has been placed or not.
Start with an empty permutation (no numbers placed yet).
Consider adding one number at a time to the permutation.
Before adding a number, check if it divides evenly by its position in the permutation (position 1, position 2, etc.). If it doesn't, don't add it – it can't be part of a self-divisible permutation.
If the number *does* divide evenly by its position, check if that number has already been used. If so, skip it.
If the number divides evenly and hasn't been used, add it to the permutation.
Update our 'memory' to record that we've extended a self-divisible partial permutation.
Repeat steps 4-8 until the permutation is complete (all numbers placed).
The value in our 'memory' after completing the full permutation will represent the total number of self-divisible permutations.

Code Implementation

def number_of_self_divisible_permutations(number):
    numbers = list(range(1, number + 1))
    count = 0
    memo = {}

    def permute(index, remaining_numbers):
        nonlocal count

        if index == number:
            count += 1
            return

        # Use tuple of remaining nums as key for memoization
        remaining_numbers_tuple = tuple(remaining_numbers)
        if (index, remaining_numbers_tuple) in memo:
            return memo[(index, remaining_numbers_tuple)]

        temp_count = 0
        for current_number in remaining_numbers:
            # Check divisibility before proceeding to prevent unnecessary computation
            if current_number % (index + 1) == 0:
                remaining_numbers_copy = remaining_numbers[:]
                remaining_numbers_copy.remove(current_number)
                permute(index + 1, remaining_numbers_copy)

        memo[(index, remaining_numbers_tuple)] = temp_count
        return temp_count

    permute(0, numbers)

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Since the problem specifies digits from 1 to n, if n is 0, there are no digits to permute, so the result should be 0.
n = 1	For n=1, the only permutation is [1], and 1 is divisible by 1, so the count is 1.
n = 2	For n=2, the permutations are [1, 2] and [2, 1]. 1 is divisible by 1 and 2 is divisible by 2 for [1,2], and 2 is divisible by 1 and 1 is not divisible by 2 for [2,1], so return 1.
Large n (e.g., n = 15)	The solution's time complexity should be carefully considered, as the number of permutations grows factorially, and memoization is critical.
n is a negative number	The problem statement defines n as an integer representing the range 1 to n, so negative values are invalid and return 0.
Input where no self-divisible permutations exist	The algorithm should correctly return 0 when no permutation satisfies the condition, such as a case where i isn't always divisible by the number at the ith position.
Integer Overflow	The count of permutations can grow very quickly, so using an appropriate data type (e.g., long in Java) to store the count is necessary to prevent integer overflow.
Recursion Depth Limits	For larger values of 'n' recursive solutions might hit the stack size limit. Consider iterative DFS with explicit stack or memoization to avoid exceeding recursion depth limits.

n = 0

How to Handle:

Since the problem specifies digits from 1 to n, if n is 0, there are no digits to permute, so the result should be 0.

n = 1

How to Handle:

For n=1, the only permutation is [1], and 1 is divisible by 1, so the count is 1.

n = 2

How to Handle:

For n=2, the permutations are [1, 2] and [2, 1]. 1 is divisible by 1 and 2 is divisible by 2 for [1,2], and 2 is divisible by 1 and 1 is not divisible by 2 for [2,1], so return 1.

Large n (e.g., n = 15)

How to Handle:

The solution's time complexity should be carefully considered, as the number of permutations grows factorially, and memoization is critical.

n is a negative number

How to Handle:

The problem statement defines n as an integer representing the range 1 to n, so negative values are invalid and return 0.

Input where no self-divisible permutations exist

How to Handle:

The algorithm should correctly return 0 when no permutation satisfies the condition, such as a case where i isn't always divisible by the number at the ith position.

Integer Overflow

How to Handle:

The count of permutations can grow very quickly, so using an appropriate data type (e.g., long in Java) to store the count is necessary to prevent integer overflow.

Recursion Depth Limits

How to Handle:

For larger values of 'n' recursive solutions might hit the stack size limit. Consider iterative DFS with explicit stack or memoization to avoid exceeding recursion depth limits.