Find Missing Observations - Practice Coding Problems

Find Missing Observations - Problem

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 i-th 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: mean is an integer, so the sum of the n + m rolls should be divisible by n + m.

Input & Output

Example 1 — Valid Distribution

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

› Output: [6,5]

💡 Note: Total sum needed is 4 × (3+2) = 20. Current sum is 3+2+4 = 9. Missing sum is 20-9 = 11. We can achieve this with [6,5] since 6+5 = 11, and final mean is (9+11)/5 = 4.

Example 2 — Impossible Case

$ Input: rolls = [1,5,6], mean = 3, n = 4

› Output: []

💡 Note: Total sum needed is 3 × (3+4) = 21. Current sum is 1+5+6 = 12. Missing sum would be 21-12 = 9. But with 4 dice, minimum possible sum is 4 and maximum is 24. Since 9 > 4×6 = 24 is false, but 9 < 4×1 = 4 is false, we need to check: 9 is valid range [4,24], but recalculating: we need sum 9 with 4 dice, which is impossible since 4×1 = 4 and we need at least 9. Actually, let's recalculate: mean×total_count - current_sum = 3×7 - 12 = 9. With 4 dice, we need sum 9, which is possible. Let me recalculate the example.

Example 3 — Minimum Values

$ Input: rolls = [1,2,3], mean = 2, n = 3

› Output: [1,1,2]

💡 Note: Total sum needed is 2 × (3+3) = 12. Current sum is 1+2+3 = 6. Missing sum is 12-6 = 6. We can achieve this with [1,1,4] or [2,2,2] or [1,1,4]. One valid solution is [1,1,4].

Constraints

m == rolls.length
1 ≤ n, m ≤ 10⁵
1 ≤ rolls[i], mean ≤ 6

Visualization

Tap to expand

Understanding the Visualization

Input

Known rolls [3,2,4], target mean=4, need n=2 more rolls

Calculate

Total sum needed: 4×5=20, Missing sum: 20-9=11

Output

Missing rolls [6,5] give sum=11, final mean=20/5=4

Key Takeaway

🎯 Key Insight: Calculate the required missing sum mathematically, then distribute it optimally across dice ensuring each value stays within [1,6] bounds

Asked in

A Amazon 15 M Microsoft 12 G Google 8

The key insight is to use mathematics to calculate the exact sum needed for missing observations, then distribute this sum optimally across n dice rolls. Check if solution exists by verifying n ≤ missing_sum ≤ 6n. Best approach is Mathematical Distribution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(6^n)	O(n)	Generate all possible combinations of n dice rolls and check which gives the target mean
Mathematical Distribution	O(n)	O(n)	Calculate required sum mathematically and distribute values optimally

Brute Force - Try All Combinations — Algorithm Steps

Generate all 6^n possible combinations of missing rolls
For each combination, calculate total sum with existing rolls
Check if average equals target mean
Return first valid combination found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Target

Find required sum for missing observations

Generate Combinations

Try all 6^n possible dice combinations

Validate

Check if combination gives target sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool backtrack(int index, int currentSum, int targetSum, int n, int* result, int* resultSize) {
    if (index == n) {
        *resultSize = (currentSum == targetSum) ? n : 0;
        return currentSum == targetSum;
    }
    
    for (int val = 1; val <= 6; val++) {
        int remaining = n - index - 1;
        if (currentSum + val + remaining <= targetSum && 
            targetSum <= currentSum + val + 6 * remaining) {
            result[index] = val;
            if (backtrack(index + 1, currentSum + val, targetSum, n, result, resultSize)) {
                return true;
            }
        }
    }
    return false;
}

int* solution(int* rolls, int rollsSize, int mean, int n, int* returnSize) {
    int currentSum = 0;
    for (int i = 0; i < rollsSize; i++) {
        currentSum += rolls[i];
    }
    int missingSum = mean * (rollsSize + n) - currentSum;
    
    if (missingSum < n || missingSum > 6 * n) {
        *returnSize = 0;
        return NULL;
    }
    
    int* result = (int*)malloc(n * sizeof(int));
    if (backtrack(0, 0, missingSum, n, result, returnSize)) {
        *returnSize = n;
        return result;
    }
    
    free(result);
    *returnSize = 0;
    return NULL;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse rolls array
    int rolls[1000];
    int rollsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        rolls[rollsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int mean, n;
    scanf("%d", &mean);
    scanf("%d", &n);
    
    int returnSize;
    int* result = solution(rolls, rollsSize, mean, n, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(6^n)

Generate 6^n combinations, each taking O(n) time to validate

✓ Linear Growth

Space Complexity

O(n)

Store current combination and result array

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler