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
Hint 1
The two sides never constrain each other, so count one side and square the result.
Hint 2
On one side,
f(i)= arrangements foriplots: the last plot is either empty (f(i-1)) or built on (f(i-2)).Hint 3
That is the Fibonacci recurrence with
f(0) = 1andf(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
- Iterate
fwithf(0) = 1,f(1) = 2,f(i) = f(i-1) + f(i-2), all modulo 10⁹ + 7. - 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 % MODJava
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