2320. Count Number of Ways to Place Houses LeetCode Solution

In this guide, you will get 2320. Count Number of Ways to Place Houses LeetCode Solution with the best time and space complexity. The solution to Count Number of Ways to Place Houses problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Count Number of Ways to Place Houses solution in C++
4. Count Number of Ways to Place Houses solution in Java
5. Count Number of Ways to Place Houses solution in Python
6. Additional Resources

Problem Statement of Count Number of Ways to Place Houses

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

2320. Count Number of Ways to Place Houses LeetCode Solution in C++

class Solution {
 public:
  int countHousePlacements(int n) {
    constexpr int kMod = 1'000'000'007;
    int house = 1;  // the number of ways ending in a house
    int space = 1;  // the number of ways ending in a space
    int total = house + space;

    for (int i = 2; i <= n; ++i) {
      house = space;
      space = total;
      total = (house + space) % kMod;
    }

    return static_cast<long>(total) * total % kMod;
  }
};
/* code provided by PROGIEZ */

2320. Count Number of Ways to Place Houses LeetCode Solution in Java

class Solution {
  public int countHousePlacements(int n) {
    final int kMod = 1_000_000_007;
    int house = 1; // the number of ways ending in a house
    int space = 1; // the number of ways ending in a space
    int total = house + space;

    for (int i = 2; i <= n; ++i) {
      house = space;
      space = total;
      total = (house + space) % kMod;
    }

    return (int) ((long) total * total % kMod);
  }
}
// code provided by PROGIEZ

2320. Count Number of Ways to Place Houses LeetCode Solution in Python

class Solution:
  def countHousePlacements(self, n: int) -> int:
    kMod = 1_000_000_007
    house = 1  # the number of ways ending in a house
    space = 1  # the number of ways ending in a space
    total = house + space

    for _ in range(2, n + 1):
      house = space
      space = total
      total = (house + space) % kMod

    return total**2 % kMod
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.