# Derangement - DP

• In how many ways can we put n different letters into n different envelopes so that ALL the letters go into the wrong envelopes?

e.g.

Envelope: e1, e2 Letters: l1, l2
l2 into e1 and l1 into e2:
Ans = 1

For 3:
e1 into l2, e2 into l3, e3 into l1 - 1 way
e1 into l3, e2 into l1, e3 into l2 - 1 more way
Ans = 2

Remember ALL letters should go into wrong envelop

• @dharaB In which company was given the problem?

• @1337c0d3r Just updated.

• @dharaB thank you very much

• @dharaB please, correct the example above. For 3, answer should be 2.

``````def numWays(n):
f = {}
def calc(n):
if n <= 1:
return 0
elif n == 2:
return 1
else:
if n not in f:
f[n] = (n - 1)* (calc(n - 1) + calc(n - 2))
return f[n]
return calc(n)``````

• @elmirap Yes for 3 its 2, my bad.
It is Dynamic Programming Problem. In interview I was close to first answer from here(https://www.quora.com/In-how-many-ways-can-we-put-4-different-letters-into-4-different-envelopes-so-that-all-the-letters-go-into-the-wrong-envelopes)

Forgot to multiply with (n-1) , although folks as Addepar are pretty good to help and encouraging!
Like this problem, it is not standard DP.

• @dharaB, Yes, there is a recursive relation with memoization. It is clear that for the first letter we have n -1 possibility, but for the second there are
n - 1 or n - 2 choices depending on the position of the first letter

• Here is the bottom up DP equivalent of @elmirap 's solution

``````    private int countWrongEnvelopWays(int n) {

if (n <= 1) return 0;
if (n == 2) return 1;

int minusOne = 1;
int minusTwo = 0;

for (int i = 3; i <= n; i++) {
int temp = minusOne;
minusOne = (i - 1) * (minusOne + minusTwo);
minusTwo = temp;
}

return minusOne;
}
``````

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