Is Count Number of Ways to Place Houses easy or hard?

The problem is rated Medium because recognizing the Fibonacci recurrence is the main challenge. Once you identify that the arrangement constraint matches the classic no-consecutive-ones problem, the implementation becomes straightforward.

Count Number of Ways to Place Houses Python/Java solution

Both Python and Java implementations follow the same Fibonacci-style DP recurrence. Maintain two variables representing dp[i-1] and dp[i-2], update them while iterating to n, and square the final count to account for both sides. Always apply modulo 1e9+7 to keep values within integer limits.

How to solve Count Number of Ways to Place Houses in O(n)?

Treat each side of the street independently and count the number of binary arrangements of length n without consecutive 1s. Use the recurrence dp[i] = dp[i-1] + dp[i-2] with base cases dp[1] = 2 and dp[2] = 3. The result for one side is squared to include both sides of the street. Apply modulo 1e9+7 during calculations.

What is the best approach for Count Number of Ways to Place Houses?

Dynamic Programming using the Fibonacci recurrence is the most practical solution. For one side of the street, the number of valid placements follows dp[i] = dp[i-1] + dp[i-2]. After computing the result for n plots, square it to account for both sides. The solution runs in O(n) time and O(1) space with state compression.

Is Count Number of Ways to Place Houses asked at Google/Amazon/Meta?

Problems involving Fibonacci-style dynamic programming and adjacency constraints frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often ask for counting valid arrangements or binary strings without consecutive elements.

What data structure is used in Count Number of Ways to Place Houses?

The solution mainly uses dynamic programming with simple integer variables or a small DP array. The recurrence only depends on the previous two states, so the implementation typically keeps two variables instead of a full array.

What is the time complexity of Count Number of Ways to Place Houses?

The standard dynamic programming solution runs in O(n) time because it iterates through all plots once while maintaining two previous states. Space complexity can be reduced to O(1). An optimized approach using matrix exponentiation computes the Fibonacci recurrence in O(log n) time.

Description Hints 3 Solution Video 8:47

2320. Count Number of Ways to Place Houses

Medium44.4% acceptance4 companies

There is a street with n * 2 plots, where there are n plots on each side of the street. The plots on each side are numbered from 1 to n. On each plot, a house can be placed.

Return the number of ways houses can be placed such that no two houses are adjacent to each other on the same side of the street. Since the answer may be very large, return it modulo 10⁹ + 7.

Note that if a house is placed on the i^th plot on one side of the street, a house can also be placed on the i^th plot on the other side of the street.

Example 1:

Input: n = 1
Output: 4
Explanation: 
Possible arrangements:
1. All plots are empty.
2. A house is placed on one side of the street.
3. A house is placed on the other side of the street.
4. Two houses are placed, one on each side of the street.

Example 2:

Input: n = 2
Output: 9
Explanation: The 9 possible arrangements are shown in the diagram above.

Constraints:

1 <= n <= 10⁴

Asked at 4 companies

Nagarro

Google Amazon Microsoft

Topics

Dynamic Programming

Hints open one at a time

Hint 1

Try coming up with a DP solution for one side of the street.

Hint 2

The DP for one side of the street will bear resemblance to the Fibonacci sequence.

Hint 3

The number of different arrangements on both side of the street is the same.

8:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution