leetcode

commit 4f19154e443722de5388535c3f43646feb615f7c
parent dac21b6c1b10e6792b00aa6aff0fbe508dc8e5b0
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 19 Dec 2025 09:58:15 -0700

1434. number of ways to wear different hats to each other

Diffstat:
A
num_ways_wear_hats.c
 | 
62
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
num_ways_wear_hats.py
 | 
48
++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 110 insertions(+), 0 deletions(-)
diff --git a/num_ways_wear_hats.c b/num_ways_wear_hats.c
@@ -0,0 +1,62 @@
+// 1434. Number of Ways to Wear Different Hats to Each Other
+#include "leetcode.h"
+
+/*
+ * there are 'n' people and 40 types of hats labeled from 1 to 40. given a 2d
+ * integer array 'hats', where 'hats[i]' is a list of all hats preferred by the
+ * i'th person. return the number of ways that 'n' people can wear different
+ * hats from each other. since the answer may be too large, return it modulo
+ * 10^9 + 7.
+ */
+
+int numberWays(int **hats, int hatsSize, int *hatsColSize) {
+  static int mod = 1e9 + 7;
+  int **hat_ppl = (int **)malloc(41 * sizeof(int *));
+  for (int i = 0; i < hatsSize; i++)
+    hat_ppl[i] = (int *)malloc(hatsSize * sizeof(int));
+  int hat_cnt[41] = {0};
+  for (int i = 0; i < hatsSize; i++)
+    for (int j = 0; j < hatsColSize[i]; j++)
+      hat_ppl[hats[i][j]][hat_cnt[hats[i][j]]++] = i;
+  int *dp = (int *)calloc(1 << hatsSize, sizeof(int));
+  dp[0] = 1;
+  for (int i = 1; i <= 40; i++) {
+    int *new_dp = (int *)malloc((1 << hatsSize) * sizeof(int));
+    memset(new_dp, dp[i], (1 << hatsSize) * sizeof(int));
+    for (int mask = 0; mask < (1 << hatsSize); mask++) {
+      for (int j = 0; j < hat_cnt[i]; j++) {
+        int person = hat_ppl[i][j];
+        if (!(mask & (1 << person))) {
+          int new_mask = mask | 1 << person;
+          new_dp[new_mask] = (new_dp[new_mask] + dp[mask]) % mod;
+        }
+      }
+    }
+    memset(dp, new_dp[i], (1 << hatsSize) * sizeof(int));
+    free(new_dp);
+  }
+  int ans = dp[(1 << hatsSize) - 1];
+  for (int i = 0; i < hatsSize; i++)
+    free(hat_ppl[i]);
+  free(hat_ppl);
+  free(dp);
+  return ans;
+}
+
+int main() {
+  int h1i[3][2] = {{3, 4}, {4, 5}, {5}};
+  int h2i[2][3] = {{3, 5, 1}, {3, 5}};
+  int h3i[4][4] = {{1, 2, 3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4}};
+  struct two_d_arr *h1 =
+      two_d_arr_init(ARRAY_SIZE(h1i), ARRAY_SIZE(h1i[0]), h1i);
+  struct two_d_arr *h2 =
+      two_d_arr_init(ARRAY_SIZE(h2i), ARRAY_SIZE(h2i[0]), h2i);
+  struct two_d_arr *h3 =
+      two_d_arr_init(ARRAY_SIZE(h3i), ARRAY_SIZE(h3i[0]), h3i);
+  printf("%d\n", numberWays(h1->arr, h1->row_size, h1->col_size)); // expect: 1
+  printf("%d\n", numberWays(h2->arr, h2->row_size, h2->col_size)); // expect: 4
+  printf("%d\n", numberWays(h3->arr, h3->row_size, h3->col_size)); // expect: 24
+  two_d_arr_free(h1);
+  two_d_arr_free(h2);
+  two_d_arr_free(h3);
+}
diff --git a/num_ways_wear_hats.py b/num_ways_wear_hats.py
@@ -0,0 +1,48 @@
+# 1434. Number of Ways to Wear Different Hats to Each Other
+
+"""
+there are 'n' people and 40 types of hats labeled from 1 to 40. given a 2d
+integer array 'hats', where 'hats[i]' is a list of all hats preferred by the
+i'th person. return the number of ways that 'n' people can wear different
+hats from each other. since the answer may be too large, return it modulo
+10^9 + 7.
+"""
+
+
+class Solution(object):
+    def numberWays(self, hats):
+        """
+        :type hats: List[List[int]]
+        :rtype: int
+        """
+        mod = 10**9 + 7
+        hat_ppl = [[] for i in range(41)]
+        for i, j in enumerate(hats):
+            for k in j:
+                hat_ppl[k].append(i)
+        hat_ppl = list(filter(lambda x: x, hat_ppl))
+        hat_cnt, ppl_cnt = len(hat_ppl), len(hats)
+        if hat_cnt < ppl_cnt:
+            return 0
+
+        def dp(i, mask):
+            if bin(mask).count("1") == ppl_cnt:
+                return 1
+            if i == hat_cnt:
+                return 0
+            res = dp(i + 1, mask)
+            for j in hat_ppl[i]:
+                if mask & (1 << j) == 0:
+                    mask |= 1 << j
+                    res += dp(i + 1, mask)
+                    mask ^= 1 << j
+            return res % mod
+
+        return dp(0, 0)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.numberWays(hats=[[3, 4], [4, 5], [5]]))
+    print(obj.numberWays(hats=[[3, 5, 1], [3, 5]]))
+    print(obj.numberWays(hats=[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]))