2320. Count Number of Ways to Place Houses

• Time: $O(n)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public: int countHousePlacements(int n) { constexpr int kMod = 1'000'000'007; int house = 1; // # of ways ending w/ house int space = 1; // # of ways ending w/ space int total = house + space; for (int i = 2; i <= n; ++i) { house = space; space = total; total = (house + space) % kMod; } return static_cast(total) * total % kMod; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public int countHousePlacements(int n) { final int kMod = 1_000_000_007; int house = 1; // # of ways ending w/ house int space = 1; // # of ways ending w/ 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); } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution: def countHousePlacements(self, n: int) -> int: kMod = 1_000_000_007 house = 1 # # of ways ending w// house space = 1 # # of ways ending w// space total = house + space for _ in range(2, n + 1): house = space space = total total = (house + space) % kMod return total**2 % kMod