2028. Find Missing Observations

Medium
Description

有 n + m 顆骰子的結果，已知 m 顆骰子的值 rolls 和所有骰子的平均值 mean。求出缺失的 n 顆骰子的可能結果。每顆骰子值在 1-6 之間。若無解回傳空陣列。

Example:

Input: rolls = [3,2,4,3], mean = 4, n = 2 Output: [6,6]

Intuition#

核心思路：算出缺失骰子的總和，然後盡量平均分配到每顆骰子，確保每顆都在 1-6 之間。

  • 總和 = mean * (n + m)，缺失總和 = 總和 - rolls 的和
  • 缺失總和必須在 [n, 6n] 之間才有解（每顆最少 1、最多 6）
  • 分配策略：每顆先分 missingSum / n，剩餘 missingSum % n 分散加到各顆

Approaches#

⭐1: 數學計算 + 平均分配#

  • 概念: 計算缺失總和，檢查可行性後平均分配
  • 時間複雜度: O(m + n) - 計算 rolls 的和 + 填入結果
  • 空間複雜度: 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: 貪心分配#

  • 概念: 逐顆分配，每顆取 min(6, 剩餘可用的最大值) 和 max(1, 剩餘不得已的最小值)
  • 時間複雜度: O(m + n)
  • 空間複雜度: 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: 受限分配問題——計算總需求後平均分配，用餘數微調
  • 關鍵技巧: base + 1 分給前 remainder 個，base 分給剩下的，是處理整除分配餘數的標準做法
Backward 2013. Detect Squares