leetcode

commit f132056ba8ae6c1164dabad9eceb9c5e587d5ffb
parent 9aaab2ea9c483997ba3a9c1235cd38125fa68d69
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri,  2 Jan 2026 20:30:34 -0700

1411. number of wways to paint n x 3 grid

Diffstat:
A
num_ways_paint_nx3_grid.c
 | 
26
++++++++++++++++++++++++++
A
num_ways_paint_nx3_grid.py
 | 
27
+++++++++++++++++++++++++++

2 files changed, 53 insertions(+), 0 deletions(-)
diff --git a/num_ways_paint_nx3_grid.c b/num_ways_paint_nx3_grid.c
@@ -0,0 +1,26 @@
+// 1411. Number of Ways to Paint N × 3 Grid
+#include "leetcode.h"
+
+/*
+ * you have a 'grid' of size 'n x 3' and you want to paint each cell of the grid
+ * with exactly one of the three colours: red, yellow, or green while making
+ * sure that no two adjacent cells have the same colour. given 'n' the number of
+ * rows of the grid, return the number of ways you can paint this 'grid'. as the
+ * answer may grow large, the answer must be computer modulo 10e9 + 7.
+ */
+
+int numOfWays(int n) {
+  long a1 = 6, a2 = 6, b1, b2, mod = 1e9 + 7;
+  for (int i = 1; i < n; ++i) {
+    b1 = a1 * 3 + a2 * 2;
+    b2 = a1 * 2 + a2 * 2;
+    a1 = b1 % mod;
+    a2 = b2 % mod;
+  }
+  return (a1 + a2) % mod;
+}
+
+int main() {
+  printf("%d\n", numOfWays(1));    // expect: 12
+  printf("%d\n", numOfWays(5000)); // expect: 30228214
+}
diff --git a/num_ways_paint_nx3_grid.py b/num_ways_paint_nx3_grid.py
@@ -0,0 +1,27 @@
+# 1411. Number of Ways to Paint N × 3 Grid
+
+"""
+you have a 'grid' of size 'n x 3' and you want to paint each cell of the grid
+with exactly one of the three colours: red, yellow, or green while making
+sure that no two adjacent cells have the same colour. given 'n' the number of
+rows of the grid, return the number of ways you can paint this 'grid'. as the
+answer may grow large, the answer must be computer modulo 10e9 + 7.
+"""
+
+
+class Solution(object):
+    def numOfWays(self, n):
+        """
+        :type n: int
+        :rtype: int
+        """
+        a1, a2, mod = 6, 6, 10**9 + 7
+        for i in range(n - 1):
+            a1, a2 = a1 * 3 + a2 * 2, a1 * 2 + a2 * 2
+        return (a1 + a2) % mod
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.numOfWays(n=1))
+    print(obj.numOfWays(n=5000))