Shared my C++ Solution with explanation based on the example in wikipedia


  • 0

    Thanks for @shuhua points out some potential error, I would check it later. And he posts O(1) space version In his post @shuhua post

    In Wikipedia, there is a clean example Wikipedia Link
    I will shared my understanding about this example

    Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number. Let us assume that the first person takes hat i. There are n − 1 ways for the first person to make such a choice. There are now two possibilities, depending on whether or not person i takes hat 1 in return:

    1. Person i does not take the hat 1. This case is equivalent to solving the problem with n − 1 persons and n − 1 hats: each of the remaining n − 1 people has precisely 1 forbidden choice from among the remaining n − 1 hats (i's forbidden choice is hat 1).
    2. Person i takes the hat 1. Now the problem reduces to n − 2 persons and n − 2 hats.

    Firstly, We define dp[i] represents number of derangemen in permutation(1...n)

    Secondly, Suppose We know the value about dp[1]...dp[n-1]. We want to compute dp[i]

    For example, At the beginning, there be n hats numbered 1..n, and n peroson numbered 1..n
    Hats : 1, 2, 3, 4, 5, 6, 7, .... n
    Person : 1, 2, 3, 4, 5, 6, 7, ... n

    If first person take hat i (!= 1)
    and now
    Hats : 1, 2, 3, 4, .. i - 1, i + 1, .... n
    Person : 2, 3, 4, ..i - 1, i, i + 1.. n

    There are now two possibilities, depending on whether or not person i takes hat 1

    1. If person i takes hat 1
      Hats : 2, 3, 4, .. i -1, i + 1, ... n
      Person : 2, 3, 4, .. i - 1, i + 1, ...n
      and above problem equivalent to the subproblem dp[i-2], Because there are 2 person take hat of different index .

    2. If person i doesn't takes hat 1. This problem equivalent to subproblem dp[i-1]. You can assume person i is person 1, he doesn't takes hat 1.
      Hats : 1, 2, 3, 4, ... i - 1, i + 1, ..n
      Person : "i", 2, 3, 4, ... i -1, i + 1, .. n

    3. After that, The first person can takes i range from (2...n) = n-1 choice.

    So. We get the recursion formula dp[i] = (dp[i-1] + dp[i-2]) * (n-1)

    Reference code

    class Solution {
    public:
        int findDerangement(int n) {
            if(n == 1)
                return 0;
            vector<unsigned long long> dp(n + 1);
            dp[2] = 1;
            for(int i = 3; i <= n; ++i){
                dp[i] = (dp[i-1] + dp[i-2]) * (i - 1) % mod;
                
            }
            return static_cast<int>(dp[n]);
        }
    private:
        const int mod = pow(10, 9) + 7;
    };
    

  • 1
    S

    Thanks for sharing your idea, but I am afraid there is a potential error due to overflow.
    Here your dp element is of type long, which is at least 32 bits (check stackoverflow). Assuming it is 32-bit, then the maximum it can represent is about 2.147e9. Therefore, in your expression (dp[i-1] + dp[i-2]) * (i - 1), the temporary result may lead to overflow of long since the maximum of dp element may be about 1e9 while i can be as large as 1e6. In such case, (dp[i-1] + dp[i-2]) * (i - 1) will give a negative long and it is further processed by modulus.
    To avoid such overflow, a wider type like unsigned long long should be used, as I have done in my answer.
    I am quite confusing why you can still pass all the test cases.
    Besides, there is no need to store all the dp elements, which makes a O(n) space complexity. It is enough to just remember the previous two elements, which gives O(1) space.


  • 0

    @shuhua
    I get you points,
    Firstly, maybe It's more secure to use unsigned long long. I would check the this later, I remember in some 64-bit system, long type is 64bits~, I have to take a nap now~, Thank you for pointing out.

    And secondly, I know this problem can be solved with O(1) space, But for make the explanation more understandable, I prefect to using O(N) space to explain the problem~ Maybe I should be added "O(1) space version "at the end~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.