2320. Count Number of Ways to Place Houses Medium

1/**
2 * [2320] Count Number of Ways to Place Houses
3 *
4 * 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.
5 * 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 10^9 + 7.
6 * Note that if a house is placed on the i^th plot on one side of the street, a house can also be placed on the i^th plot on the other side of the street.
7 *  
8 * Example 1:
9 *
10 * Input: n = 1
11 * Output: 4
12 * Explanation:
13 * Possible arrangements:
14 * 1. All plots are empty.
15 * 2. A house is placed on one side of the street.
16 * 3. A house is placed on the other side of the street.
17 * 4. Two houses are placed, one on each side of the street.
18 *
19 * Example 2:
20 * <img alt="" src="https://assets.leetcode.com/uploads/2022/05/12/arrangements.png" style="width: 500px; height: 500px;" />
21 * Input: n = 2
22 * Output: 9
23 * Explanation: The 9 possible arrangements are shown in the diagram above.
24 *
25 *  
26 * Constraints:
27 *
28 * 1 <= n <= 10^4
29 *
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/count-number-of-ways-to-place-houses/
34// discuss: https://leetcode.com/problems/count-number-of-ways-to-place-houses/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    const MOD: i64 = 1000000007;
40    pub fn count_house_placements(n: i32) -> i32 {
41        let (mut place, mut not_place) = (1, 1);
42        for _ in 2..=n {
43            let x = (place + not_place) % Self::MOD;
44            place = not_place % Self::MOD;
45            not_place = x;
46        }
47        (((place + not_place) % Self::MOD).pow(2) % Self::MOD) as i32
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2320() {
59        assert_eq!(Solution::count_house_placements(1), 4);
60        assert_eq!(Solution::count_house_placements(2), 9);
61    }
62}
63