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 have also calculated the average value of the n + m rolls.
You are given an integer array rolls of length m where rolls[i] is the value of the ith observation. You are also given the two integers mean and n.
Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.
The average value of a set of k numbers is the sum of the numbers divided by k.
Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.
Example 1:
Input: rolls = [3,2,4,3], mean = 4, n = 2
Output: [6,6]
Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.
Example 2:
Input: rolls = [1,5,6], mean = 3, n = 4
Output: [2,3,2,2]
Explanation: The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.
Example 3:
Input: rolls = [1,2,3,4], mean = 6, n = 4
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing rolls are.
Constraints:
- m == rolls.length
- 1 <= n, m <= 105
- 1 <= rolls[i], mean <= 6
역시 수학문제는 다르다.
꽤나 기발한 풀이법이었음.
Key point는 나머지를 이용하는 것이다.
1. C++
class Solution {
public:
vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
int m = rolls.size();
vector<int> ans;
int sum = 0;
for(int x : rolls){
sum += x;
}
int test1 = mean*(m+n) - sum;
int total_sum = mean*(m+n);
int target = total_sum - sum;
// for impossible case
if(test1 < n || test1 > 6*n) return {};
int mean_val = target / n;
int remind = target % n;
for(int i=0;i<n;i++){
if(remind>0){
ans.push_back(mean_val+1); //there is reminder
remind--;
}
else ans.push_back(mean_val);
}
return ans;
}
};
2. C
C는 return 값을 malloc으로 해줘야한다는 조건이 붙어서 좀 구찮긴 하다;;
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* missingRolls(int* rolls, int rollsSize, int mean, int n, int* returnSize) {
int sum = 0;
int m = rollsSize;
for(int i=0;i<m;i++){
sum += rolls[i];
}
int target = mean*(m+n) - sum;
// Impossible case
if(target < n || target > 6*n){
*returnSize = 0;
return NULL;
}
int* ans = (int*)malloc(n*sizeof(int));
int mean_val = target / n;
int remind = target % n;
for(int j=0;j<n;j++){
if(j<remind){
ans[j] = mean_val+1;
}else ans[j] = mean_val;
}
*returnSize = n;
return ans;
}
3. Python
역시 비슷한 맥락으로 함 해보자.
파이썬은 정수 나눗셈이 좀 다를 수도 있겠다.
class Solution:
def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
sum_val = sum(rolls)
m = len(rolls)
target = mean*(m+n) - sum_val
if target < n or target > 6*n : return []
ans = []
mean_val = target // n
remind = target % n
for i in range(n):
if i < remind : ans.append(mean_val+1)
else : ans.append(mean_val)
return ans