Count Number of Ways to Place Houses — Medium Problem & Solution

Problem statement

A street has n plots on each of its two sides, numbered 1 to n. A house may be built on any plot, but no two houses on the same side may be adjacent. The two sides are independent.

Return the number of ways to place houses, modulo 10⁹ + 7.

Example 1

Input: n = 1
Output: 4
Explanation: Each side is free to have a house or not: 2 × 2.

Example 2

Input: n = 2
Output: 9
Explanation: Three arrangements per side — empty, first only, second only — squared.

Example 3

Input: n = 3
Output: 25
Explanation: Five arrangements per side.

Constraints

• 1 <= n <= 10^4

How to solve Count Number of Ways to Place Houses

The sides are independent, so the answer is f(n)² where f(n) counts the ways to place non-adjacent houses along one row of n plots. f satisfies the Fibonacci recurrence: leave the last plot empty and the rest is f(n-1), or build on it and the plot before must be empty, leaving f(n-2).

Approach

1. Iterate f with f(0) = 1, f(1) = 2, f(i) = f(i-1) + f(i-2), all modulo 10⁹ + 7.
2. Return f(n) · f(n) mod 10⁹ + 7.

Why it works

Squaring is valid precisely because the constraint is per-side — a house across the street is never adjacent. And the recurrence needs the square taken after the modulo: f(n) can be close to 10⁹, so the product must be reduced, which in 64-bit languages is fine and in JavaScript needs a split multiplication or care that the product stays under 2⁵³.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• Squaring two residues near 10⁹ overflows a 32-bit integer — compute in 64 bits.
• f(1) = 2, not 1: a single plot may be empty or built on.
• The two sides are counted independently, not jointly.

Reference solution

Python

def countHousePlacements(n: int) -> int:
    MOD = 10**9 + 7
    prev, cur = 1, 2
    for _ in range(2, n + 1):
        prev, cur = cur, (prev + cur) % MOD
    return cur * cur % MOD

JavaScript

var countHousePlacements = function(n) {
    var MOD = 1000000007;
    var prev = 1, cur = 2;
    for (var i = 2; i <= n; i++) {
        var next = (prev + cur) % MOD;
        prev = cur;
        cur = next;
    }
    // cur can approach 1e9, so split the square to stay inside 2^53.
    var hi = Math.floor(cur / 65536), lo = cur % 65536;
    return ((hi * cur % MOD) * 65536 + lo * cur) % MOD;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Find the Winner of the Circular Game Medium
• Stone Game VII Medium
• Number of Ways to Divide a Long Corridor Medium
• Count Ways to Group Overlapping Ranges Medium
• Count Number of Texts Medium
• Number of Ways to Reach a Position After Exactly k Steps Medium