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 Sets of K Non-Overlapping Line Segments

Number: 1725

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

We are given n points on a 1-D plane with the iᵗʰ point at x = i (i from 0 to n-1). The goal is to pick exactly k non-overlapping line segments such that each segment covers at least two points (with endpoints specified by integer coordinates). Line segments may share endpoints and need not cover all points. The answer should be returned modulo 10⁹+7.

Key Insights

  • The segments are non overlapping but are allowed to share endpoints.
  • Each segment must cover at least 2 consecutive points.
  • A combinatorial transformation can be applied by “inserting” gaps between segments.
  • The counting can be reduced to computing a binomial coefficient. In fact, one can show that the answer is given by:
    Answer = C(n + k - 1, 2k)
  • Precomputing factorials and modular inverses helps to quickly compute combination values modulo 10⁹+7.

Space and Time Complexity

Time Complexity: O(n + k) for precomputing factorials/modular inverses (assuming n and k are such that n+k is the maximum value needed).
Space Complexity: O(n + k) due to storage of factorials and modular inverses.

Solution

The problem can be solved using a combinatorial approach. The main idea is to interpret drawing a segment as "consuming" two endpoints while still allowing segments to touch (share endpoints). By a careful transformation, the count of valid ways to choose k segments from n points reduces to choosing 2k endpoints with additional k "gaps" (which represent mandatory extra spacing between the segments). This results in a combinatorial formula: C(n + k - 1, 2k).

To compute the combination value modulo 10⁹+7 efficiently, we precompute factorials and then modular inverses (using Fermat’s little theorem since the modulus is prime). Finally, we compute the binomial coefficient C(n + k - 1, 2k).

This method bypasses more complicated dynamic programming recurrences and directly computes the answer in a straightforward manner.

Code Solutions

# Python solution using precomputation for factorial and inverse factorial

MOD = 10**9 + 7

def modInverse(x, mod=MOD):
    # Fermat's little theorem for modular inverse under prime mod
    return pow(x, mod - 2, mod)

def nCr(n, r, fact, inv_fact):
    # if r is invalid, return 0
    if r < 0 or r > n:
        return 0
    return (fact[n] * inv_fact[r] % MOD) * inv_fact[n - r] % MOD

def numberOfSets(n: int, k: int) -> int:
    # Maximum value for factorial computation is n + k - 1.
    max_val = n + k - 1
    fact = [1] * (max_val + 1)
    inv_fact = [1] * (max_val + 1)
    
    # Precompute factorials modulo MOD
    for i in range(1, max_val + 1):
        fact[i] = fact[i - 1] * i % MOD
        
    # Precompute inverses for factorials
    inv_fact[max_val] = modInverse(fact[max_val])
    for i in range(max_val, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD
        
    # Use combinatorial formula: Answer = C(n + k - 1, 2k)
    return nCr(n + k - 1, 2 * k, fact, inv_fact)

# Example usage:
print(numberOfSets(4, 2))  # Expected output: 5
print(numberOfSets(3, 1))  # Expected output: 3
← Back to All Questions