Count Number of Ways to Place Houses

Medium
1043.

Count Number of Ways to Place Houses

Count Number of Ways to Place Houses is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Oracle interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countHousePlacements = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Number of Ways to Place Houses — Problem & Solution

Count Number of Ways to Place Houses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Number of Ways to Place Houses is a medium coding problem on dynamic programming and math, asked in Amazon, Google and Oracle interviews.

  • Difficulty: Medium
  • Topics: Dynamic Programming, Math
  • Asked at: Amazon, Google, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Count Number of Ways to Place Houses

  1. Hint 1

    The two sides never constrain each other, so count one side and square the result.

  2. Hint 2

    On one side, f(i) = arrangements for i plots: the last plot is either empty (f(i-1)) or built on (f(i-2)).

  3. Hint 3

    That is the Fibonacci recurrence with f(0) = 1 and f(1) = 2.

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

Java

public static int countHousePlacements(int n) {
    final long MOD = 1000000007L;
    long prev = 1, cur = 2;
    for (int i = 2; i <= n; i++) {
        long next = (prev + cur) % MOD;
        prev = cur;
        cur = next;
    }
    return (int) (cur * cur % MOD);
}

C++

int countHousePlacements(int n) {
    const long long MOD = 1000000007LL;
    long long prev = 1, cur = 2;
    for (int i = 2; i <= n; i++) {
        long long next = (prev + cur) % MOD;
        prev = cur;
        cur = next;
    }
    return (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming