Last Updated: 8 Apr, 2022

Moving Average

Moderate

Solve now

Problem statement

A stock price is dynamic. Its value can change multiple times in a fraction of a second or remain unchanged for several minutes. Analysing the dynamics of stock price change can provide an indication of a forthcoming uptrend or downtrend in that stock. One such indicator is simple moving averages. Now, Harry wants to analyse the price trend of the stock on the basis of moving averages (MA).

Let’s consider a moving average of 2-day and 4-day, respectively. A 2-day moving average is calculated by taking an average of the closing price of 2 consecutive days. A 4-day moving average is calculated by taking an average closing price of 4 consecutive days. Now, according to experts whenever a faster moving average curve (2-day MA) cuts the slower moving average (4-day MA) from below, then it is an indication of an uptrend in the stock. Similarly, whenever a faster-moving averages curve (2-day MA) cuts the slower moving average curve (4-day MA) from above, then it is an indication of the downtrend in the stock.

Help Harry in computing the number of uptrends and downtrends in the given time for which the data is provided.

In this graph, there are three lines indicating stock closing price, moving average of two days and four days. Now we can see that between 13th and 15th there is an intersection. It is known as a downtrend when the moving average of fewer days is cut downwards the more days moving average and vice versa.

Note1 – There will be no day1 moving average for 2-day MA. Similarly, there will be no day1, day2, and day3 moving average for 4-day MA. In general, there will be no X-1, X-2, Y-1, Y-2, etc. day point for the X-day and Y-day moving average curve.

Note2 – All the computation has to be accurate up to 6 digits after the decimal point.

EXAMPLE:

Input: 'X' = 2, 'Y' = 3, 'N' = 4, A = [2.0, 4.0, 3.0, 2.0]

Output: "1"

As moving average of length ‘2’ till index ‘2’ is ‘((4.0+3.5)/2)’=’3.5’, and the moving average of length ‘3’ till index ‘2’ is  ‘((2.0+4.0+3.0)/3)’=’3.0’. As we move to the next index ‘3’, the moving average of length ‘2’ becomes ‘2.5’ and of length ‘3’ becomes ‘3.0’. So moving average to length ‘2’ changed smaller at current index from bigger at last index from moving average of length ‘3’, so they are cutting each other between this period.

Input Format :

The first line will contain the integer 'T', denoting the number of test cases.

For each test case, the first line contains two space-separated integers which are the moving average days ‘X’ and ‘Y’.

Second-line contains an integer ‘N’ denoting the number of stock prices.

The third line contains ‘N’ space-separated decimal values denoting the closing price of the stock for ‘N’ days.

Output format :

For each test case, print the number of times the stock will give an uptrend or downtrend.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 10
1 <= ‘N’ <= 10^5
1 <= 'X', ‘Y’ <= 10^5
1.0 <= ‘A[i]’ <= 10^4
Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

We will maintain the ‘X’ size and ‘Y’ size moving average. Now we will iterate over each ‘I’ ranging from max( ‘X’, ‘Y’ ) to ’ N’. For each ‘I’, compare the value of moving averages at the current index with the previous index. If ‘X’ size moving average was smaller than the ‘Y’ size moving average at the previous index but at the current index if ‘X’ size moving average is greater than ‘Y’ size moving average or vice-versa. It means that there is an intersection between their curves. Or there is an uptrend or downtrend.

Algorithm :

Maintain 6 variable (‘sum_x_cur’,’sum_y_cur’,’sum_x_prev’,’sum_y_prev’,’final_ans’,’x_big’).
Where ‘x_big’ will tell us that ‘X’ size moving average is big or ’Y’ size.
‘x_big’=-1 indicates that they have the same value from start for each index.
Iterate over each ‘I’ such that max(X,Y) <= ‘I’ <= ‘N’
For each ‘I’ update ‘sum_x_prev’=’sum_x_cur’ and ‘sum_y_prev’=’sum_y_cur’.
Then calculate the moving sum of length ‘X’ and ‘Y’ till the current index ‘I’ by updating ‘sum_x_cur’ and ‘sum_y_cur’.
And then check
- If ‘(‘x_big’ == ‘-1’ || ‘sum_x_cur/x’ == ’sum_y_cur/y’)’ then update the x_big value if, ‘sum_x_cur/x’ != ’sum_y_cur/y’.
- Else if ‘((‘sum_x_cur’ / ’X’ > ‘sum_y_cur’ / ’Y’) ^ ’x_big’ )’ Increment the ‘final_ans’ by 1 and change ‘x_big’ to 1-’x_big’.
Return ‘final_ans’.

Solve now