Count number of ways to place houses

Dynamic Programming

43.8% acceptance

Feb 25, 2026

643

202

There is a street with n * 2 plots, where there are n plots on each side of the street. Return the number of ways houses can be placed such that no two houses are adjacent on the same side. Since the answer may be very large, return it modulo 10^9 + 7.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn count_house_placements(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    // f(n) = number of ways for one side: f(1)=2, f(2)=3, f(n)=f(n-1)+f(n-2)
    let mut a = 1i64; // f(0) = 1
    let mut b = 2i64; // f(1) = 2
    for _ in 1..n {
      let c = (a + b) % MOD;
      a = b;
      b = c;
    }
    // answer = f(n)^2 mod MOD, where b is f(n) after loop
    let side = b;
    ((side * side) % MOD) as i32
  }
}