1866. Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode Solution
In this guide, you will get 1866. Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode Solution with the best time and space complexity. The solution to Number of Ways to Rearrange Sticks With K Sticks Visible problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Ways to Rearrange Sticks With K Sticks Visible
There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.
For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.
Given n and k, return the number of such arrangements. Since the answer may be large, return it 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.
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.
Constraints:
1 <= n <= 1000
1 <= k <= n
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(nk)
1866. Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode Solution in C++
class Solution {
public:
long rearrangeSticks(int n, int k) {
if (n == k)
return 1;
if (k == 0)
return 0;
if (dp[n][k])
return dp[n][k];
return dp[n][k] = (rearrangeSticks(n - 1, k - 1) +
rearrangeSticks(n - 1, k) * (n - 1)) %
kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
vector<vector<int>> dp = vector<vector<int>>(1001, vector<int>(1001));
}; /* code provided by PROGIEZ */
1866. Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode Solution in Java
class Solution {
public int rearrangeSticks(int n, int k) {
if (n == k)
return 1;
if (k == 0)
return 0;
if (dp[n][k] != 0)
return dp[n][k];
return dp[n][k] = (int) (((long) rearrangeSticks(n - 1, k - 1) +
(long) rearrangeSticks(n - 1, k) * (n - 1)) %
kMod);
}
private static final int kMod = 1_000_000_007;
private int[][] dp = new int[1001][1001];
} // code provided by PROGIEZ
1866. Number of Ways to Rearrange Sticks With K Sticks Visible LeetCode Solution in Python
class Solution:
@functools.lru_cache(None)
def rearrangeSticks(self, n: int, k: int) -> int:
if n == k:
return 1
if k == 0:
return 0
return (self.rearrangeSticks(n - 1, k - 1) +
self.rearrangeSticks(n - 1, k) * (n - 1)) % self.kMod
kMod = 1_000_000_007 # code by PROGIEZ
