有 n + m 顆骰子的結果，已知 m 顆骰子的值
rolls和所有骰子的平均值mean。求出缺失的 n 顆骰子的可能結果。每顆骰子值在 1-6 之間。若無解回傳空陣列。
Example:
Input: rolls = [3,2,4,3], mean = 4, n = 2 Output: [6,6]
Intuition
TIP
核心思路：算出缺失骰子的總和，然後盡量平均分配到每顆骰子，確保每顆都在 1-6 之間。
- 總和 =
mean * (n + m)，缺失總和 = 總和 -rolls的和 - 缺失總和必須在
[n, 6n]之間才有解（每顆最少 1、最多 6） - 分配策略：每顆先分
missingSum / n，剩餘missingSum % n分散加到各顆
Approaches
⭐ 1. Math + Even Allocation — O(m + n) / O(n)
- Idea: 計算缺失總和，檢查可行性後平均分配
- Time:
O(m + n)- 計算 rolls 的和 + 填入結果 - Space:
O(n)- 結果陣列
class Solution {
fun missingRolls(rolls: IntArray, mean: Int, n: Int): IntArray {
val m = rolls.size
val totalSum = mean * (n + m)
val missingSum = totalSum - rolls.sum()
// 檢查可行性
if (missingSum < n || missingSum > 6 * n) return intArrayOf()
val base = missingSum / n
val remainder = missingSum % n
val result = IntArray(n) { base }
// 前 remainder 顆骰子各多加 1
for (i in 0 until remainder) {
result[i]++
}
return result
}
}2. Greedy Allocation — O(m + n) / O(n)
- Idea: 逐顆分配，每顆取 min(6, 剩餘可用的最大值) 和 max(1, 剩餘不得已的最小值)
- Time:
O(m + n) - Space:
O(n)
class Solution {
fun missingRolls(rolls: IntArray, mean: Int, n: Int): IntArray {
val m = rolls.size
var remaining = mean * (n + m) - rolls.sum()
if (remaining < n || remaining > 6 * n) return intArrayOf()
val result = IntArray(n)
for (i in 0 until n) {
// 確保剩下的骰子每顆至少可分 1、至多可分 6
val maxVal = minOf(6, remaining - (n - 1 - i))
val minVal = maxOf(1, remaining - 6 * (n - 1 - i))
result[i] = maxVal
remaining -= result[i]
}
return result
}
}🔑 Takeaways
- Pattern: 受限分配問題——計算總需求後平均分配，用餘數微調
- Key trick:
base + 1分給前remainder個，base分給剩下的，是處理整除分配餘數的標準做法