We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Rearrange Sticks With K Sticks Visible

Number: 1996

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

(A short summary or question text)

Given n uniquely-sized sticks with lengths 1 through n, the task is to count the number of arrangements such that exactly k sticks are visible from the left. A stick is visible if there is no longer stick to its left. Return the answer modulo 10^9 + 7.

Key Insights

  • A stick is visible if it is the tallest up to that point in the arrangement.
  • The largest stick (length n) is always visible if placed at the front.
  • If the largest stick is placed as leftmost visible stick, then the remaining n - 1 sticks need to be arranged to have exactly k - 1 visible sticks.
  • If the largest stick is inserted in any other position, it will be hidden, and the subproblem remains with n - 1 sticks and k visible sticks.
  • This leads to the recurrence: dp[n][k] = dp[n - 1][k - 1] + (n - 1) * dp[n - 1][k].

Space and Time Complexity

Time Complexity: O(n * k) because each state dp[i][j] for i in 1..n and j in 1..k is computed. Space Complexity: O(n * k) due to the 2D DP table used to store subproblem solutions.

Solution

We use dynamic programming with a 2D table dp, where dp[i][j] represents the number of arrangements using i sticks with exactly j sticks visible from the left. The main recurrence is:

  1. dp[i][j] = dp[i - 1][j - 1] when the ith stick (largest among those considered) is placed so that it's visible.
  2. dp[i][j] += (i - 1) * dp[i - 1][j] when the largest stick is inserted into any position where it is not visible. A modulus operation at each step ensures that numbers remain manageable and meet the problem requirements.

Code Solutions

MOD = 10**9 + 7

def rearrangeSticks(n, k):
    # Initialize dp table with dimensions (n+1) x (k+1)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[1][1] = 1  # Base case: one stick and one visible stick

    # Fill the dp table for each number of sticks from 2 to n
    for i in range(2, n + 1):
        for j in range(1, min(i, k) + 1):
            # Case 1: the largest stick is visible
            dp[i][j] = dp[i - 1][j - 1] % MOD
            # Case 2: the largest stick is hidden and can be inserted in any of the (i-1) positions
            dp[i][j] = (dp[i][j] + (i - 1) * dp[i - 1][j]) % MOD
    return dp[n][k]

# Example usage
print(rearrangeSticks(3, 2))  # Expected output: 3
← Back to All Questions