ProbToreal: IARCS AVERAGE ( Tutorial + Solution )

=>Try Yourself First. For help Scroll Down . Make sure you are tried enough. This will help you to learn something new for sure.

Problem Link: http://opc.iarcs.org.in/index.php/problems/AVERAGE

Problem Clearance:

You are given an Array of N elements. You are said to figure out the total number of AVERAGE elements among this elements. Which means if A[i] is an element and if it is an average of any two element ( let us A[j] and A[k] where 1=<j , k<=N [ but j, k both could not be same as i at the same time ] ) in the list.

Suppose, A[] = { 2, 2 ,2 } then answer will be 3. Because all 3 elements could be a Average of any two element .

Observation:

Look at the constraint . So O(N^2) solution will pass at 3 second time limit. But a O(N^3) solution will not pass. So what will be the thought to solve this problem. Take an Array and sort the Elements.

Idea 1: And make a notation that the element of current index is present . Now run a O(N^2) loop. Make average of two element at index i & j. Now check notation of this result's presence. Sorry the limit of each element is MAXINT (i.e. 2^31-1) . So array will not work.

Idea 2: So upgrade the previous idea and use a Map instead of an Array and check the presence of result. Wait a bit !! Do you know Map costs O(log2N) for accessing each element. So for all N^2 let's calculate complexity O(N^2*log2N) = ( 10^4 * 10^4 * log2(10^8) ) = 2,657,542,476 which is greater than 3*10^8 ( Problem's Time Limit is: 3s ). So time limit occurs.

Idea 3: So what do you think? Are you thinking to use an unordered_map STL whose accessing complexity is O(1) ? Sorry !! It's not possible . Because unordered_map only works with C++11. But the compiler in IARCS site is not C++11. Do you wait till the upgrade it ? I don't even know they will upgrade it or not ? 😢

Idea 4: What are you thinking now ? For each ith index you will add the element of jth index an store them into an array . As the array is previously sorted you will get sorted sum. And then make a Binary Search on the sorted list and if found the ith element then count increases by one .... Sorry that will not also work . Beacuse that will also cost O(NlgN) .

So ?? All idea failed ?? If you tried all the idea above and make some wrong submission for this problem then you ready to grab the correct idea. I don't know whether there are other ideas to solve this problem but I worked with the following one.

The idea to Solve:

Please keep in mind that ( X + Y ) / 2 = K could also be written as ( X + Y ) = 2*K . Here we will consider the average calculation by ( X + Y ) = 2*K for avoiding floating point exception purpose.

At first you need to sort the list . Then for each ith index you have to declare two pointer . Let one is left pointer that will go left from the current position and the another one is right pointer that wil move to the right side from the current position. Now for each ith index what you have to check is whether you could express it as an average of two integer that are currently at left pointer and right pointer or by summing A[i] with A[i-1] or A[i+1] ( previous index and current index ) .

Make sure you did not add the left and right pointer elemnent when Left and Right pointer is same . So , when you figured out that your current sum of elements of left and right pointers is greater than 2*A[i] then you need to deacrese the left pointer by one. Because going right of the right pointer will not give you the 2*A[i] value. But going to left side can give a result which could be an AVERAGE element .When you figure out your elements at pointer's sum is Equal to 2*A[i] or you have same value at previous and current index as mentioned before then count will increase by one and as you have pointed out ith index as an AVERAGE element then terminate the current loop . Do the similar process for each of the ith index.