Problem Link - Average
Problem Statement
You are given a sequence of integers a[1],a[2],...,a[N]. An element a[k] is said to be an average element if there are indices i,j (with i≠j) such that a[k] = (a[i] +a[j])/2.
In the sequence
3~~~~~~7~~~~~~10~~~~~~22~~~~~~17~~~~~~15
for i=1,j=5 and k=3, we get a[k] = (a[i] +a[j])/2. Thus a[3] = 10 is an average element in this sequence. You can check that a[3] is the only average element in this sequence.
Consider the sequence
3~~~~~~7~~~~~~10~~~~~~3~~~~~~18
With i=1,j=4 and k=1 we get a[k] = (a[i] +a[j])/2. Thus a[1]=3 is an average element. We could also choose i=1,j=4 and k=4 and get a[k] = (a[i] +a[j])/2. You can check that a[1] and a[4] are the only average elements of this sequence.
On the other hand, the sequence
3~~~~~~8~~~~~~11~~~~~~17~~~~~~30
has no average elements.
Your task is to count the number of average elements in the given sequence.
Approach
The main idea is to find all pairs of numbers in the sequence, calculate their average, and check if this average exists as another element in the sequence. To do this efficiently, we first count how many times each number appears in the sequence using a frequency map. This allows us to quickly verify if the calculated average is part of the sequence.
For every pair of numbers, we compute their sum and divide it by 2. If this value is an integer (not a fraction) and exists in the sequence, it is a potential average element. To ensure that we count each average element only once, we mark it as processed after counting it. This avoids duplicating results and keeps the process efficient.
Time Complexity
The time complexity is O(N^2), as we need to check all pairs of elements in the sequence.
Space Complexity
The space complexity is O(N), due to the use of a frequency map to store the occurrences of each number.