Leetcode Daily Question 05/09/2024 - 2028. Find Missing Observations

Problem Description:

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.

from typing import List
class Solution:
  def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
    m = len(rolls)
    roll_sum = sum(rolls)
    target_total = (m + n) * mean - roll_sum
    
    quotient, remainder = divmod(target_total, n)
    return [quotient + (1 if i < remainder else 0) for i in range(n)]

Explanation:

This question boils down to finding a valid partition of length n such that it perturbs the mean to our target mean.

To do this, we need to calculate what is the total that we need to add to our current sum to make the solution valid.

def missingRolls(rolls, mean, n):
  m = len(rolls)
  roll_sum = sum(rolls)
  target_total = (m + n) * mean - roll_sum

Then we need to figure out the partition required.

We do this by first evenly distributing the target total. Then we distribute the remainder until we run out.

To make this abit more efficient, we can use the in-built divmod(a,b) method in python.

This returns the tuple (a // b, a % b), hence the function name.

Finally we use list comprehension to assign the values. We index through from 0 to n - 1 and add 1 if this index is less than remainder (this is the same as running a nested for loop).

quotient, remainder = divmod(targt_total, n)
return [quotient + (1 if i < remainder else 0) for i in range(n)]

The time complexity is O(n) as we iterate through n elements to assign its value at the end.

The space complexity is O(n) as we store the resulting array of length n.

The full solution can be found near the top of the page.