2320. Count Number of Ways to Place Houses Solution | FC

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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⁴

Approach overview

Problem Overview: You are given n plots on each side of a street. Each plot can either contain a house or remain empty, but adjacent plots on the same side cannot both contain houses. The task is to count the total number of valid placement configurations across both sides of the street.

The key observation: the two sides of the street are independent. First compute the number of valid arrangements for a single row of n plots with no two adjacent houses. Then square the result to account for both sides.

Approach 1: Dynamic Programming with Fibonacci Relation (Time: O(n), Space: O(n) or O(1))

For a single side of the street, this becomes the classic problem of counting binary strings of length n with no consecutive 1s. Let dp[i] represent the number of valid ways to arrange houses in the first i plots. If the current plot is empty, any valid arrangement of i-1 plots works. If the current plot contains a house, the previous plot must be empty, so the count comes from i-2. This gives the recurrence dp[i] = dp[i-1] + dp[i-2]. The sequence is identical to Fibonacci numbers. After computing the result for one side, square it to account for both sides. Use modulo 1e9+7 to avoid overflow.

This approach is straightforward and efficient. You iterate once from 1 to n, updating two previous states. With state compression, the space drops from O(n) to O(1). This method is commonly used in dynamic programming problems where the current state depends on a small number of previous states.

Approach 2: Matrix Exponentiation (Time: O(log n), Space: O(1))

The Fibonacci recurrence can be represented as a matrix transformation. The relation F(n) = F(n-1) + F(n-2) can be expressed using the matrix [[1,1],[1,0]]. Raising this matrix to the power n allows you to compute the result in logarithmic time using fast exponentiation.

Matrix exponentiation repeatedly squares the transition matrix while reducing the exponent by half each step. This reduces the complexity from linear to logarithmic time. After computing the Fibonacci value for one street side, square the result to get the total configurations across both sides.

This technique appears frequently in problems involving linear recurrences and is a standard optimization when n becomes very large. It is closely related to topics like matrix exponentiation and mathematical recurrence transformations.

Recommended for interviews: The dynamic programming approach with the Fibonacci relation is what most interviewers expect. It shows that you recognize the adjacency constraint and convert it into a recurrence. Matrix exponentiation demonstrates deeper algorithmic knowledge but is typically discussed as an optimization after presenting the DP solution.

Approach 1: Dynamic Programming with Fibonacci Relation

Identify the problem as a variation of the Fibonacci sequence solving adjacency constraints for house placement. Establish a dynamic programming relation where dp[i] defines the number of ways to arrange houses on i plots with no two adjacent.

Without losing generality, analyze one side of the street. For n plots, the problem becomes a classic non-adjacent placement problem, solvable by a Fibonacci-like approach. This leads to relation dp[i] = dp[i-1] + dp[i-2], since if the plot i is filled, plot i-1 can't be, and if plot i is not filled, it follows the i-1 arrangement.

Since both sides of the street are independent, compute the total ways considering both sides as the square of the computed dp[n] value modulo 10^9 + 7.

Python

def countHousePlacements(n):
    MOD = 10**9 + 7
    if n == 1: return 4
    prev, cur = 2, 3
    for i in range(3, n + 1):
        prev, cur = cur, (prev + cur) % MOD
    return (cur * cur) % MOD

print(countHousePlacements(2))

Java

public class HousePlacement {
    public int countHousePlacements(int n) {
        int MOD = 1000000007;
        if (n == 1) return 4;
        long prev = 2, cur = 3;
        for (int i = 3; i <= n; ++i) {
            long temp = (prev + cur) % MOD;
            prev = cur;
            cur = temp;
        }
        return (int)((cur * cur) % MOD);
    }
    public static void main(String[] args) {
        HousePlacement hp = new HousePlacement();
        System.out.println(hp.countHousePlacements(2));
    }
}

C++

#include <iostream>
using namespace std;
#define MOD 1000000007

int countHousePlacements(int n) {
    if (n == 1) return 4;
    long long prev = 2, cur = 3;
    for (int i = 3; i <= n; ++i) {
        long long next = (prev + cur) % MOD;
        prev = cur;
        cur = next;
    }
    return (cur * cur) % MOD;
}

int main() {
    int n = 2;
    cout << countHousePlacements(n) << endl;
    return 0;
}

JavaScript

function countHousePlacements(n) {
    const MOD = 1e9 + 7;
    if (n === 1) return 4;
    let prev = 2, cur = 3;
    for (let i = 3; i <= n; ++i) {
        [prev, cur] = [cur, (prev + cur) % MOD];
    }
    return (cur * cur) % MOD;
}

console.log(countHousePlacements(2));

#include <stdio.h>
#define MOD 1000000007

int countHousePlacements(int n) {
    if (n == 1) return 4;
    long long prev = 2, cur = 3;
    for (int i = 3; i <= n; ++i) {
        long long next = (prev + cur) % MOD;
        prev = cur;
        cur = next;
    }
    return (cur * cur) % MOD;
}

int main() {
    int n = 2;
    printf("%d\n", countHousePlacements(n));
    return 0;
}

using System;

class Program {
    static int MOD = 1000000007;
    public static int CountHousePlacements(int n) {
        if (n == 1) return 4;
        long prev = 2, cur = 3;
        for (int i = 3; i <= n; ++i) {
            long next = (prev + cur) % MOD;
            prev = cur;
            cur = next;
        }
        return (int)((cur * cur) % MOD);
    }

    static void Main() {
        Console.WriteLine(CountHousePlacements(2));
    }
}

A Python solution leveraging tuple unpacking to efficiently calculate the Fibonacci-like sequence, multiplying the final result by itself to represent both sides of the street, and taking modulo to handle large numbers.

Complexity

Time Complexity: O(n) for iteration over n plots

Space Complexity: O(1) due to constant space usage

Try this approach in the editor

Approach 2: Matrix Exponentiation

Another efficient method to solve this problem, especially for large values of n, is Matrix Exponentiation, which offers improved time complexity for Fibonacci-related sequence generation. The Fibonacci sequence or similar can be represented using matrix multiplication, allowing for efficient computation through exponentiation using binary methods.

Python

def multiply(F, M, MOD):
    x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD
    y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD
    z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD
    w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD
    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w


def power(F, n, MOD):
    if n == 0 or n == 1:
        return
    M = [[1, 1], [1, 0]]
    power(F, n // 2, MOD)
    multiply(F, F, MOD)
    if n % 2 != 0:
        multiply(F, M, MOD)


def fib(n, MOD):
    F = [[1, 1], [1, 0]]
    if n == 0:
        return 0
    power(F, n - 1, MOD)
    return F[0][0]


def countHousePlacements(n):
    MOD = 10**9 + 7
    fib_n_plus_2 = fib(n + 2, MOD)
    return (fib_n_plus_2 * fib_n_plus_2) % MOD

print(countHousePlacements(2))

Java

public class HousePlacement {
    static final int MOD = 1000000007;

    private static void multiply(long[][] F, long[][] M) {
        long x = (F[0][0] * M[0][0] % MOD + F[0][1] * M[1][0] % MOD) % MOD;
        long y = (F[0][0] * M[0][1] % MOD + F[0][1] * M[1][1] % MOD) % MOD;
        long z = (F[1][0] * M[0][0] % MOD + F[1][1] * M[1][0] % MOD) % MOD;
        long w = (F[1][0] * M[0][1] % MOD + F[1][1] * M[1][1] % MOD) % MOD;

        F[0][0] = x;
        F[0][1] = y;
        F[1][0] = z;
        F[1][1] = w;
    }

    private static void power(long[][] F, int n) {
        if (n == 0 || n == 1) return;
        long M[][] = { { 1, 1 }, { 1, 0 } };

        power(F, n / 2);
        multiply(F, F);

        if (n % 2 != 0) multiply(F, M);
    }

    private static int fibonacci(int n) {
        long F[][] = { { 1, 1 }, { 1, 0 } };
        if (n == 0) return 0;
        power(F, n - 1);
        return (int) F[0][0];
    }

    public int countHousePlacements(int n) {
        int fib_n_plus_2 = fibonacci(n + 2);
        return (int) ((long) fib_n_plus_2 * fib_n_plus_2 % MOD);
    }

    public static void main(String[] args) {
        HousePlacement hp = new HousePlacement();
        System.out.println(hp.countHousePlacements(2));
    }
}

C++

#include <iostream>
using namespace std;
#define MOD 1000000007

typedef long long ll;

void multiply(ll F[2][2], ll M[2][2]) {
    ll x = (F[0][0] * M[0][0] % MOD + F[0][1] * M[1][0] % MOD) % MOD;
    ll y = (F[0][0] * M[0][1] % MOD + F[0][1] * M[1][1] % MOD) % MOD;
    ll z = (F[1][0] * M[0][0] % MOD + F[1][1] * M[1][0] % MOD) % MOD;
    ll w = (F[1][0] * M[0][1] % MOD + F[1][1] * M[1][1] % MOD) % MOD;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(ll F[2][2], int n) {
    if (n == 0 || n == 1) return;
    ll M[2][2] = {{1, 1}, {1, 0}};

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0) multiply(F, M);
}

int fib(int n) {
    ll F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0)
        return 0;
    power(F, n - 1);
    return F[0][0];
}

int countHousePlacements(int n) {
    int fib_n_plus_2 = fib(n + 2);
    return (1LL * fib_n_plus_2 * fib_n_plus_2) % MOD;
}

int main() {
    int n = 2;
    cout << countHousePlacements(n) << endl;
    return 0;
}

JavaScript

function multiply(F, M, MOD) {
    const x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD;
    const y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD;
    const z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD;
    const w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

function power(F, n, MOD) {
    if (n === 0 || n === 1) return;
    const M = [[1, 1], [1, 0]];
    power(F, Math.floor(n / 2), MOD);
    multiply(F, F, MOD);

    if (n % 2 !== 0) multiply(F, M, MOD);
}

function fib(n, MOD) {
    if (n === 0) return 0;
    const F = [[1, 1], [1, 0]];
    power(F, n - 1, MOD);
    return F[0][0];
}

function countHousePlacements(n) {
    const MOD = 1e9 + 7;
    const fib_n_plus_2 = fib(n + 2, MOD);
    return (fib_n_plus_2 * fib_n_plus_2) % MOD;
}

console.log(countHousePlacements(2));

#include <stdio.h>
#define MOD 1000000007

void multiply(long long F[2][2], long long M[2][2]) {
    long long x = (F[0][0] * M[0][0] % MOD + F[0][1] * M[1][0] % MOD) % MOD;
    long long y = (F[0][0] * M[0][1] % MOD + F[0][1] * M[1][1] % MOD) % MOD;
    long long z = (F[1][0] * M[0][0] % MOD + F[1][1] * M[1][0] % MOD) % MOD;
    long long w = (F[1][0] * M[0][1] % MOD + F[1][1] * M[1][1] % MOD) % MOD;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(long long F[2][2], int n) {
    if (n == 0 || n == 1) return;
    long long M[2][2] = {{1, 1}, {1, 0}};

    power(F, n / 2);
    multiply(F, F);

    if (n % 2 != 0) multiply(F, M);
}

int fib(int n) {
    long long F[2][2] = {{1, 1}, {1, 0}};
    if (n == 0) return 0;
    power(F, n - 1);
    return F[0][0];
}

int countHousePlacements(int n) {
    int fib_n_plus_2 = fib(n + 2);
    return (1LL * fib_n_plus_2 * fib_n_plus_2 % MOD);
}

int main() {
    int n = 2;
    printf("%d\n", countHousePlacements(n));
    return 0;
}

The Python solution employs nested functions for matrix operations, keeping it modular and efficient using a recursive matrix power function. This approach manages large integers, benefitting from Python’s inherent large number support.

Complexity

Time Complexity: O(log n) using matrix binomial approach

Space Complexity: O(1), with the bulk of operations handled in small function scope

Try this approach in the editor

Approach 3: Dynamic Programming

Since the placement of houses on both sides of the street does not affect each other, we can consider the placement on one side only, and then square the number of ways for one side to get the final result modulo.

We define f[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot having a house. We define g[i] to represent the number of ways to place houses on the first i+1 plots, with the last plot not having a house. Initially, f[0] = g[0] = 1.

When placing the (i+1)-th plot, there are two cases:

If the (i+1)-th plot has a house, then the i-th plot must not have a house, so the number of ways is f[i] = g[i-1];
If the (i+1)-th plot does not have a house, then the i-th plot can either have a house or not, so the number of ways is g[i] = f[i-1] + g[i-1].

Finally, we square f[n-1] + g[n-1] modulo to get the answer.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the street.

TypeScript

function countHousePlacements(n: number): number {
    const f = new Array(n);
    const g = new Array(n);
    f[0] = g[0] = 1n;
    const mod = BigInt(10 ** 9 + 7);
    for (let i = 1; i < n; ++i) {
        f[i] = g[i - 1];
        g[i] = (f[i - 1] + g[i - 1]) % mod;
    }
    const v = f[n - 1] + g[n - 1];
    return Number(v ** 2n % mod);
}

func countHousePlacements(n int) int {
	const mod = 1e9 + 7
	f := make([]int, n)
	g := make([]int, n)
	f[0], g[0] = 1, 1
	for i := 1; i < n; i++ {
		f[i] = g[i-1]
		g[i] = (f[i-1] + g[i-1]) % mod
	}
	v := f[n-1] + g[n-1]
	return v * v % mod
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Fibonacci Relation	Time Complexity: O(n) for iteration over n plots Space Complexity: O(1) due to constant space usage
Matrix Exponentiation	Time Complexity: O(log n) using matrix binomial approach Space Complexity: O(1), with the bulk of operations handled in small function scope
Dynamic Programming	–

Approach

Complexity

Dynamic Programming with Fibonacci Relation

Time Complexity: O(n) for iteration over n plots

Space Complexity: O(1) due to constant space usage

Matrix Exponentiation

Time Complexity: O(log n) using matrix binomial approach

Space Complexity: O(1), with the bulk of operations handled in small function scope

Dynamic Programming

–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with Fibonacci Relation	O(n)	O(1) optimized	Best general solution. Simple recurrence and easy to implement in interviews.
Matrix Exponentiation	O(log n)	O(1)	Useful when n is extremely large or when optimizing Fibonacci-style recurrences.

Frequently asked questions

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.

Count Number of Ways to Place Houses solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Fibonacci Relation

Approach 2: Matrix Exponentiation

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Count Number of Ways to Place Houses solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Fibonacci Relation

Approach 2: Matrix Exponentiation

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems