Skip to main content
Talentd

Find Missing Observations - Solution & Explanation

MediumArrayMathSimulation14 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given several observed dice rolls and the overall mean of all rolls (observed + missing). Each roll is between 1 and 6. The task is to reconstruct the n missing rolls so the final average matches the given mean. If it is impossible to form valid dice values, return an empty array.

Approach 1: Calculate Missing Sum and Distribute Among Rolls (Time: O(m + n), Space: O(n))

This approach relies on simple math and array operations. First compute the total sum required for all rolls using mean * (m + n), where m is the number of observed rolls. Subtract the sum of the observed array to get the total value the missing rolls must contribute. If this value is outside the feasible range [n, 6n], there is no valid solution because dice values must stay between 1 and 6.

Once the required sum is valid, distribute it across n elements. Start by assigning the base value missingSum // n to each position and distribute the remainder by incrementing elements by one until the total matches the required sum. This guarantees all values remain within bounds while keeping the distribution balanced. The algorithm performs a single pass over the input and builds the result array directly.

Approach 2: Iterative Construction of Missing Rolls (Time: O(m + n), Space: O(n))

This method builds the missing sequence step by step using a greedy simulation. Compute the total missing sum the same way as the previous approach. Instead of evenly distributing values immediately, iterate through the n positions and assign a value that keeps the remaining sum feasible for the remaining slots.

At each step, choose the smallest valid value that still allows the remaining positions to stay within the dice bounds. For example, if you place x, ensure the remaining sum can still fall within [remainingSlots, 6 * remainingSlots]. This constraint check guarantees that future assignments remain valid. The process continues until all n values are assigned or the constraints fail.

This approach is useful when you want explicit control over each assignment or when explaining feasibility constraints during interviews. It makes the reasoning about bounds very clear, though it performs the same number of operations as the direct distribution method.

Recommended for interviews: The missing sum distribution approach is the most common solution because it reduces the problem to a straightforward arithmetic constraint and balanced allocation. Interviewers expect you to first verify the feasibility range [n, 6n] and then construct the result in linear time. Demonstrating the iterative feasibility check also shows strong reasoning about constraints and edge cases.

Approach 1: Calculate Missing Sum and Distribute Among Rolls

First, calculate the total required sum for n + m rolls to satisfy the given mean. Then, compute the sum of the already available rolls and determine how much more is needed from the n missing rolls. If the required sum for the missing rolls is feasible (i.e., between n and 6*n), distribute the required sum across the missing rolls aiming for an even distribution.

In this Python solution, we first calculate the total_sum that is needed by multiplying mean with n + m. We then subtract the current_sum of the known rolls from total_sum to find missing_sum, which represents the sum needed from the missing rolls. If missing_sum is not feasible (not between n and 6 * n), we return an empty array. Otherwise, we distribute the missing_sum into parts to create the missing rolls.

Code

PythonJava

Python

Java

Complexity

The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls.

Try this approach in the editor →

Approach 2: Iterative Construction of Missing Rolls

This approach iteratively builds the missing rolls by ensuring each additional roll keeps the total sum within possible bounds. Start with an empty list for the missing rolls, and iteratively add values ensuring the sum remains feasible, adjusting at each step.

In this C++ solution, we accumulate the currentSum using std::accumulate. If the calculated missingSum is valid, we initialize a result vector with all ones. We then iteratively increase each entry by a maximum possible value (up to 5, since each die can have a maximum value of 6) until the missing sum is fulfilled.

Code

C++JavaScript

C++

JavaScript

Complexity

The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage.

Try this approach in the editor →

Approach 3: Construction

According to the problem description, the sum of all numbers is (n + m) times mean, and the sum of known numbers is sum_{i=0}^{m-1} rolls[i]. Therefore, the sum of the missing numbers is s = (n + m) times mean - sum_{i=0}^{m-1} rolls[i].

If s \gt n times 6 or s \lt n, it means there is no answer that satisfies the conditions, so we return an empty array.

Otherwise, we can evenly distribute s to n numbers, that is, the value of each number is s / n, and the value of s bmod n numbers is increased by 1.

The time complexity is O(n + m), where n and m are the number of missing numbers and known numbers, respectively. Ignoring the space consumption of the answer, the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Calculate Missing Sum and Distribute Among Rolls

The time complexity is O(n + m), where n and m are the number of missing and known observations, respectively, due to the sum calculations and array operations. The space complexity is O(n), for the storage of the missing rolls.

Iterative Construction of Missing Rolls

The time complexity is O(n + m) due to the sum calculation and iteration over the missing rolls. The space complexity is O(n) for the missing rolls' storage.

Construction—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Calculate Missing Sum and DistributeO(m + n)O(n)General case. Clean mathematical solution with minimal logic.
Iterative Construction of Missing RollsO(m + n)O(n)When explaining feasibility constraints step-by-step or simulating assignments.

Video Solution

Find Missing Observations - Leetcode 2028 Weekly Contest Problem - Python • NeetCode • 10,491 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find Missing Observations easy or hard?
Find Missing Observations is rated Medium difficulty on LeetCode with an acceptance rate around 57%. The implementation is straightforward once you identify the missing sum constraint, but recognizing the feasibility range [n, 6n] is the key insight.
Find Missing Observations Python/Java solution
A typical Python or Java solution computes the required missing sum, checks if it lies within [n, 6n], then fills an array with base value missingSum // n and distributes the remainder across elements. Both implementations run in O(m + n) time and use O(n) extra space.
How to solve Find Missing Observations in O(n)?
First compute the required total sum from the given mean. Subtract the sum of known rolls to get the missing sum. If the value is outside [n, 6n], return an empty array. Otherwise distribute the sum across n elements using integer division and remainder handling, which builds the result in linear time.
What is the best approach for Find Missing Observations?
The most efficient approach computes the total required sum using mean * (m + n), subtracts the sum of observed rolls, and distributes the remaining value across the missing rolls. A feasibility check ensures the sum lies within [n, 6n]. This solution runs in O(m + n) time and O(n) space.
Is Find Missing Observations asked at Google/Amazon/Meta?
This problem represents a typical interview pattern involving arithmetic constraints and array construction. Variants of this question appear in coding interviews at large tech companies because they test reasoning about bounds, feasibility checks, and linear-time array construction.
What data structure is used in Find Missing Observations?
The problem primarily uses arrays along with simple mathematical calculations. No advanced data structures are required. The key idea is computing sums and constructing an array that satisfies the constraints of dice values between 1 and 6.
What is the time complexity of Find Missing Observations?
The optimal solution runs in O(m + n) time, where m is the number of observed rolls and n is the number of missing rolls. You compute the observed sum once and construct the result array once. Space complexity is O(n) because you return the missing rolls array.

Ready to solve this problem?

Practice Find Missing Observations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Dice Roll Simulation

Next

Number of Dice Rolls With Target Sum