{"id":8598,"date":"2021-10-04T20:22:05","date_gmt":"2021-10-05T03:22:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8598"},"modified":"2021-10-04T20:28:16","modified_gmt":"2021-10-05T03:28:16","slug":"leetcode-2028-find-missing-observations","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-2028-find-missing-observations\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2028. Find Missing Observations"},"content":{"rendered":"\n

You have observations of n + m<\/code> 6-sided<\/strong> dice rolls with each face numbered from 1<\/code> to 6<\/code>. n<\/code> of the observations went missing, and you only have the observations of m<\/code> rolls. Fortunately, you have also calculated the average value<\/strong> of the n + m<\/code> rolls.<\/p>\n\n\n\n

You are given an integer array rolls<\/code> of length m<\/code> where rolls[i]<\/code> is the value of the ith<\/sup><\/code> observation. You are also given the two integers mean<\/code> and n<\/code>.<\/p>\n\n\n\n

Return an array of length <\/em>n<\/code> containing the missing observations such that the average value <\/strong>of the <\/em>n + m<\/code> rolls is exactly<\/strong> <\/em>mean<\/code>. If there are multiple valid answers, return any of them<\/em>. If no such array exists, return an empty array<\/em>.<\/p>\n\n\n\n

The average value<\/strong> of a set of k<\/code> numbers is the sum of the numbers divided by k<\/code>.<\/p>\n\n\n\n

Note that mean<\/code> is an integer, so the sum of the n + m<\/code> rolls should be divisible by n + m<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> rolls = [3,2,4,3], mean = 4, n = 2\nOutput:<\/strong> [6,6]\nExplanation:<\/strong> The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) \/ 6 = 4.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rolls = [1,5,6], mean = 3, n = 4\nOutput:<\/strong> [2,3,2,2]\nExplanation:<\/strong> The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) \/ 7 = 3.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rolls = [1,2,3,4], mean = 6, n = 4\nOutput:<\/strong> []\nExplanation:<\/strong> It is impossible for the mean to be 6 no matter what the 4 missing rolls are.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> rolls = [1], mean = 3, n = 1\nOutput:<\/strong> [5]\nExplanation:<\/strong> The mean of all n + m rolls is (1 + 5) \/ 2 = 3.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • m == rolls.length<\/code><\/li>
  • 1 <= n, m <= 105<\/sup><\/code><\/li>
  • 1 <= rolls[i], mean <= 6<\/code><\/li><\/ul>\n\n\n\n
    Solution: Math & Greedy<\/strong><\/h2>\n\n\n\n
    Total sum = (m + n) * mean
    Left = Total sum – sum(rolls) = (m + n) * mean – sum(rolls)
    If left > 6 * n or left < 1 * n, then there is no solution.
    Otherwise, we need to distribute Left into n rolls.
    There are very ways to do that, one of them is even distribution, e.g. using the average number as much as possible, and use avg + 1 to fill the gap.
    Compute the average and reminder: x = left \/ n, r = left % n.
    there will be n – r of x and r of x + 1 in the output array.<\/p>\n\n\n\n
    e.g. [1, 5, 6], mean = 3, n = 4
    Total sum = (3 + 4) * 3 = 21
    Left = 21 – (1 + 5 + 6) = 9
    x = 9 \/ 4 = 2, r = 9 % 4 = 1
    Ans = [2, 2, 2, 2+1] = [2,2,2,3]<\/p>\n\n\n\n
    Time complexity: O(m + n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \nclass Solution {\npublic:\n  vector missingRolls(vector& rolls, int mean, int n) {\n    const int m = rolls.size();    \n    int t = accumulate(begin(rolls), end(rolls), 0);\n    int left = mean * (m + n) - t;\n    if (left > 6 * n || left < n) return {};    \n    vector ans(n, left \/ n);\n    for (int i = 0; i < left % n; ++i) ++ans[i];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[31],"class_list":["post-8598","post","type-post","status-publish","format-standard","hentry","category-math","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8598","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8598"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8598\/revisions"}],"predecessor-version":[{"id":8602,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8598\/revisions\/8602"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8598"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8598"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8598"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}