A warehouse has n bins numbered 1 to n, each originally holding one item numbered the same as the bin. The items are rearranged into a new permutation p of 1..n, where p(i) is the item now placed in bin i (1-indexed). To keep the reshuffling manageable, every item may move by at most k bins from its original position: |p(i) - i| <= k must hold for every bin i.
Count how many permutations of 1..n satisfy this bounded-displacement condition for the given k.
Line 1: two integers n and k.
A single integer: the number of valid permutations.
Example 1
Input
3 0
Expected
1
Explanation
With k=0, every element must stay in its original position, so only the identity permutation 1,2,3 works, giving a count of 1.
Example 2
Input
3 1
Expected
3
Explanation
Every valid arrangement keeps each value within 1 position of its index; there are 3 such permutations: 1,2,3; 1,3,2; and 2,1,3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →