Leetcode | Maximum Compatibility Score Sum | Kotlin

devstromo · devstromo · commit b7a8d176096a · 2025-04-27T23:05:29.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p1947/DESCRIPTION.md b/leetcode/src/main/kotlin/com/devstromo/medium/p1947/DESCRIPTION.md
@@ -0,0 +1,38 @@
+# 1947. Maximum Compatibility Score Sum
+
+There is a survey that consists of `n` questions where each question's answer is either `0` (no) or `1` (yes).
+
+The survey was given to `m` students numbered from `0` to `m - 1` and `m` mentors numbered from `0` to `m - 1`. The answers of the students are represented by a 2D integer array `students` where `students[i]` is an integer array that contains the answers of the `ith` student (0-indexed). The answers of the mentors are represented by a 2D integer array `mentors` where `mentors[j]` is an integer array that contains the answers of the `jth` mentor (0-indexed).
+
+Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
+
+- For example, if the student's answers were `[1, 0, 1]` and the mentor's answers were `[0, 0, 1]`, then their compatibility score is 2 because only the second and the third answers are the same.
+
+You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
+
+Given `students` and `mentors`, return the maximum compatibility score sum that can be achieved.
+
+Example 1:
+
+Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
+Output: 8
+Explanation: We assign students to mentors in the following way:
+
+- student 0 to mentor 2 with a compatibility score of 3.
+- student 1 to mentor 0 with a compatibility score of 2.
+- student 2 to mentor 1 with a compatibility score of 3.
+  The compatibility score sum is 3 + 2 + 3 = 8.
+
+Example 2:
+
+Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
+Output: 0
+Explanation: The compatibility score of any student-mentor pair is 0.
+
+Constraints:
+
+- `m == students.length == mentors.length`
+- `n == students[i].length == mentors[j].length`
+- `1 <= m, n <= 8`
+- `students[i][k]` is either `0` or `1`.
+- `mentors[j][k]` is either `0` or `1`.
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p1947/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/medium/p1947/SolutionKt.kt
@@ -0,0 +1,38 @@
+package com.devstromo.medium.p1947
+
+class SolutionKt {
+    fun maxCompatibilitySum(students: Array<IntArray>, mentors: Array<IntArray>): Int {
+        val m = students.size
+        val n = students[0].size
+
+        // Precompute compatibility scores
+        val score = Array(m) { IntArray(m) }
+        for (i in 0 until m) {
+            for (j in 0 until m) {
+                var match = 0
+                for (k in 0 until n) {
+                    if (students[i][k] == mentors[j][k]) {
+                        match++
+                    }
+                }
+                score[i][j] = match
+            }
+        }
+
+        val dp = IntArray(1 shl m)
+
+        for (mask in 0 until (1 shl m)) {
+            val studentIndex = mask.countOneBits()
+            if (studentIndex >= m) continue
+
+            for (j in 0 until m) {
+                if ((mask and (1 shl j)) == 0) { // mentor j not yet assigned
+                    val nextMask = mask or (1 shl j)
+                    dp[nextMask] = maxOf(dp[nextMask], dp[mask] + score[studentIndex][j])
+                }
+            }
+        }
+
+        return dp[(1 shl m) - 1]
+    }
+}
diff --git a/leetcode/src/test/kotlin/com/devstromo/medium/p1947/SolutionKtUnitTest.kt b/leetcode/src/test/kotlin/com/devstromo/medium/p1947/SolutionKtUnitTest.kt
@@ -0,0 +1,42 @@
+package com.devstromo.medium.p1947
+
+import org.junit.jupiter.api.Assertions.*
+import org.junit.jupiter.api.DisplayName
+import org.junit.jupiter.api.Test
+
+class SolutionKtUnitTest {
+    private val solution = SolutionKt()
+
+    @Test
+    @DisplayName("Test Maximum Compatibility Score Sum")
+    fun testMaximumCompatibilityScoreSum() {
+        assertEquals(
+            8, solution.maxCompatibilitySum(
+                arrayOf(
+                    intArrayOf(1, 1, 0),
+                    intArrayOf(1, 0, 1),
+                    intArrayOf(0, 0, 1)
+                ),
+                arrayOf(
+                    intArrayOf(1, 0, 0),
+                    intArrayOf(0, 0, 1),
+                    intArrayOf(1, 1, 0)
+                )
+            )
+        )
+        assertEquals(
+            0, solution.maxCompatibilitySum(
+                arrayOf(
+                    intArrayOf(0, 0),
+                    intArrayOf(0, 0),
+                    intArrayOf(0, 0),
+                ),
+                arrayOf(
+                    intArrayOf(1, 1),
+                    intArrayOf(1, 1),
+                    intArrayOf(1, 1),
+                )
+            )
+        )
+    }
+}
