Question

2320. Count Number of Ways to Place Houses

中文文档

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

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

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);
  }
}

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;
  }
};

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
}

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);
}

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);
  }
}