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

Count Number of Ways to Place Houses

Number: 2397

Difficulty: Medium

Paid? No

Companies: Nagarro

Problem Description

There is a street with n * 2 plots (n on each side). On each plot, you can decide to place a house or leave it empty, with the restriction that no two houses can be adjacent on the same side. Note that houses placed on corresponding plots on opposite sides of the street do not affect each other. The task is to count the number of valid ways to place houses on the entire street modulo 10^9 + 7.

Key Insights

  • The problem can be divided into two independent subproblems (one for each side), as placing a house on the left side does not affect the right side.
  • For a single side, the problem reduces to counting the number of ways to choose plots such that no two chosen plots are adjacent.
  • For one side, if we let dp[i] be the number of valid arrangements for i plots, the recurrence becomes dp[i] = dp[i - 1] + dp[i - 2] (with appropriate base cases).
  • For a single side, the base cases are: dp[0] = 1 (empty set) and dp[1] = 2 (either place a house or not).
  • Since both sides are independent, the final answer is the square of the number of valid arrangements for one side, taken modulo 10^9 + 7.

Space and Time Complexity

Time Complexity: O(n), where n is the number of plots on one side, due to the single loop to compute the dp sequence. Space Complexity: O(1), as we can optimize the recurrence to use only two variables instead of an array.

Solution

To solve the problem, we first compute the number of valid arrangements for one side using dynamic programming. The recurrence relation is:   dp[i] = dp[i - 1] + dp[i - 2] with base cases:   dp[0] = 1 (an empty street)   dp[1] = 2 (either place a house or leave it empty)

After computing dp[n] for one side, the result for the entire street (both sides) is (dp[n] * dp[n]) % mod, where mod = 10^9 + 7.

This solution uses dynamic programming with constant space optimization and directly squares the one-side count to get the final result.

Code Solutions

# Python solution using constant space dynamic programming

MOD = 10**9 + 7

def countHousePlacements(n: int) -> int:
    # Base case for n = 0
    if n == 0:
        return 1

    # Initialize base values: dp0 represents dp[0], dp1 represents dp[1]
    dp0, dp1 = 1, 2

    # Compute dp[i] for i from 2 to n using recurrence dp[i] = dp[i-1] + dp[i-2]
    for i in range(2, n + 1):
        dp_curr = (dp1 + dp0) % MOD
        dp0, dp1 = dp1, dp_curr

    # The final answer is square of ways for one side mod MOD
    return (dp1 * dp1) % MOD

# Example usage:
if __name__ == "__main__":
    n = 2
    print(countHousePlacements(n))  # Expected output: 9
← Back to All Questions