Skip to content

2320. Count Number of Ways to Place Houses

SourceWeekly Contest 299 Q2DifficultyMediumRating1607

Description

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 109 + 7.

Note that if a house is placed on the ith plot on one side of the street, a house can also be placed on the ith 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 <= 104

Solutions

Solution 1: Dynamic Programming

Thinking

The two sides of the street are independent, and adjacent plots on one side cannot both hold a house. \(n \le 10^4\); the answer is the square of one side’s count. A side search only needs whether the previous plot is occupied.

Let \(f[i]\) and \(g[i]\) be ways to fill the first \(i+1\) plots with the last one occupied or empty. Occupied forces the previous empty; empty allows either. Multiply the two sides modulo the given constant.

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def countHousePlacements(self, n: int) -> int:
        mod = 10**9 + 7
        f = [1] * n
        g = [1] * n
        for i in range(1, n):
            f[i] = g[i - 1]
            g[i] = (f[i - 1] + g[i - 1]) % mod
        v = f[-1] + g[-1]
        return v * v % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int countHousePlacements(int n) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = 1;
        g[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - 1];
            g[i] = (f[i - 1] + g[i - 1]) % mod;
        }
        long v = (f[n - 1] + g[n - 1]) % mod;
        return (int) (v * v % mod);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int countHousePlacements(int n) {
        const int mod = 1e9 + 7;
        int f[n], g[n];
        f[0] = g[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - 1];
            g[i] = (f[i - 1] + g[i - 1]) % mod;
        }
        long v = f[n - 1] + g[n - 1];
        return v * v % mod;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public class Solution {
    public int CountHousePlacements(int n) {
        const int mod = (int) 1e9 + 7;
        int[] f = new int[n];
        int[] g = new int[n];
        f[0] = g[0] = 1;
        for (int i = 1; i < n; ++i) {
            f[i] = g[i - 1];
            g[i] = (f[i - 1] + g[i - 1]) % mod;
        }
        long v = (f[n - 1] + g[n - 1]) % mod;
        return (int) (v * v % mod);
    }
}

Comments