ContainsItsAverage
SRM 807 · 2021-06-07 · by misof
Problem Statement
In this problem we are interested in sequences of integers that contain their own average.
For example, the sequence {1, 2, 3, 4, 5} is such a sequence: its average is (1+2+3+4+5) / 5 = 3, and 3 is indeed an element of the sequence.
The sequence {0, 0, 0, 0} does also contain its own average. (In this case, all four elements are equal to the average of the sequence.)
The sequence {1, 2, 3, 4, 5, 0, -15} is also such a sequence: its average is 0 and that is one of the elements of the sequence.
The sequence {1, 1, 2, 3, 5, 4} does not contain its own average: its average is 8/3 = 2.6666666 and that is not an element of this sequence (and not an integer).
The sequence {10, 20, 30, 40} has an integer average (25) but 25 is not an element of this sequence, so we are not interested in this sequence either.
Ela has shown you N-1 elements of her N-element sequence.
The values she has shown you are in the
Ela claims that the missing element is also an integer and that her sequence contains its own average.
Given that information, you now want to find the last element X of Ela's sequence.
If there are at most 100 different possible values of X, return a
Notes
- Only the elements in the input must be between 0 and 20,000,000, inclusive. The missing element may lie outside this range. (See Example #1.)
- It is guaranteed that for each input that matches the constraints each valid X fits into a 32-bit signed integer variable.
Constraints
- seq will contain between 1 and 50 elements, inclusive.
- Each element of seq will be between 0 and 20,000,000, inclusive.
{0, 0, 0}
Returns: {0 }
The only option is that the missing element is also 0. As we already know, the sequence {0, 0, 0, 0} does contain its average. For any other X, the sequence will be {0, 0, 0, X}, its average will be X/4, and that's clearly not an element of the sequence.
{1, 10, 1000, 100}
Returns: {-1106, -1061, -611, 3889 }
The sequence {1, 10, 1000, 100, -1106} has the average (1 + 10 + 1000 + 100 + (-1106)) / 5 = 5/5 = 1. And as 1 is one of the five elements of {1, 10, 1000, 100, -1106}, this sequence does contain its own average. We can easily verify that each of the other three options for X also produces a sequence that contains its own average. Please remember that the returned array must be sorted.
{500000, 400000, 200000, 100000}
Returns: {-700000, -200000, 300000, 800000, 1300000 }
{47}
Returns: {47 }
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20000000}
Returns: {-20000000, 400000, 1000000000 }
Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ContainsItsAverage with a public method vector<int> missing(vector<int> seq) · 97 test cases · 2 s / 256 MB per case