#1866
Number of Ways to Rearrange Sticks With K Sticks Visible
expert · 1170 · lc hard +32 · verified · 60.6% accepted · 755 likes · top 59%
Description
There are n sticks of distinct lengths 1 to n. Arrange all of them so that exactly k are visible from the left. A stick is visible if no taller stick stands to its left.
Return the number of such arrangements modulo 109 + 7.
Example 1:
Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.
Example 2:
Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.
Example 3:
Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 109 + 7) ways to rearrange the sticks such that exactly 11 sticks are visible.
Code
1
2
3