Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2320.html

2320. Count Number of Ways to Place Houses

• Difficulty: Medium.
• Related Topics: Dynamic Programming.
• Similar Questions: Climbing Stairs, House Robber.

Problem

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

Solution (Java, C++, Python)

• Java
• Python
• C++
• Go
• TypeScript
• C#

• class Solution {
      public int countHousePlacements(int n) {
          // algo - 1st solve one side  of the street
          // think 0 - space , 1 - house
          // if n = 1 then we can take one 0 and one 1 (total ways = 2)
          // if n = 2 then 00 , 01 , 10 , 11 but we cant take 11 as two house cant be adjacent.
          // so the 1 ended string will be only 1 which is same as previous 0 ended string and 0 ended
          // string are 2 which is previous sum(total ways)
          // apply this formula for n no's
          long mod = 1000000007;
          long space = 1;
          long house = 1;
          long sum = space + house;
          while (--n > 0) {
              house = space;
              space = sum;
              sum = (house + space) % mod;
          }
          // as street has two side
          return (int) ((sum * sum) % 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:
      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
  
  ############
  
  # 2320. Count Number of Ways to Place Houses
  # https://leetcode.com/problems/count-number-of-ways-to-place-houses/
  
  class Solution:
      def countHousePlacements(self, n: int) -> int:
          M = 10 ** 9 + 7
          res = 0
          
          @cache
          def go(k):
              if k == 0: return 1
              if k == 1: return 2
  
              return go(k - 1) + go(k - 2)
          
          return (go(n) ** 2) % M
  
  

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

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions