Introduction

In this blog post, we will explore how to solve the LeetCode problem "2320" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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

Explanation

Here's the solution to the problem, along with the explanation:

• High-Level Approach:

  • Calculate the number of ways to arrange houses on one side of the street such that no two houses are adjacent. This can be done using dynamic programming or Fibonacci numbers.
  • Square the result from the previous step, because each arrangement on one side can be combined with any arrangement on the other side independently.
  • Take the modulo at each step to prevent overflow.

• Complexity:

  • Runtime Complexity: O(n)
  • Storage Complexity: O(1)

Code

    def count_house_placements(n: int) -> int:
    """
    Calculates the number of ways houses can be placed on both sides of a street
    such that no two houses are adjacent on the same side.

    Args:
        n: The number of plots on each side of the street.

    Returns:
        The number of ways houses can be placed, modulo 10^9 + 7.
    """
    MOD = 10**9 + 7

    # dp[i] stores the number of ways to arrange houses on one side with i plots
    # such that no two houses are adjacent.

    # dp[i] = dp[i-1] + dp[i-2]
    # It's similar to fibonacci. dp[1]=2 (either house or no house), dp[2]=3(HH,HE,EE), dp[3] = 5

    if n == 1:
      one_side_ways = 2
    else:

      a = 1  # dp[i-2]
      b = 2  # dp[i-1]
      for _ in range(2, n + 1):
          temp = (a + b) % MOD
          a = b
          b = temp

      one_side_ways = b

    return (one_side_ways * one_side_ways) % MOD