[Solved] Count Number of Ways to Place Houses LeetCode Contest Problem

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

Solution

Explanation

Inspired by @lordofmountain
One side has no effect to the other.
The number of way on one side is fibo sequence.
return fibo * fibo in the end.

Complexity

Time O(n)
Space O(1)

Java

    public int countHousePlacements(int n) {
        int a = 1, b = 1, c = 2, mod = (int)1e9 + 7;
        for (int i = 0; i < n; ++i) {
            c = (a + b) % mod;
            a = b;
            b = c;
        }
        return (int)(1L * b * b % mod);
    }

C++

    int countHousePlacements(int n) {
        int a = 1, b = 1, c = 2, mod = 1e9 + 7;
        for (int i = 0; i < n; ++i) {
            c = (a + b) % mod;
            a = b;
            b = c;
        }
        return 1L * b * b % mod;
    }

Python

    def countHousePlacements(self, n):
        a, b, mod = 1, 1, 10**9 + 7
        for i in range(n):
            a, b = b, (a + b) % mod
        return b * b % mod

Solution 2: Fast Pow

Time O(logn)
Space O(1)

Python

    def fib(self, n: int) -> int:
        a, b, c, d, mod = 1, 1, 0, 1, 10 ** 9 + 7
        while n:
            if n & 1:
                a, b = a * c + b * d, a * d + b * c + b * d
                n -= 1
            else:
                c, d = c * c + d * d, 2 * c * d + d * d
                n >>= 1
            a, b, c, d = a % mod, b % mod, c % mod, d % mod
        return a

    def countHousePlacements(self, n):
        return self.fib(n + 1) ** 2 % (10 ** 9 + 7)

Happy Learning – If you require any further information, feel free to contact me.