Rotate Function
Given an array of integers ‘ARR’. Let Ck be defined as an array obtained after cyclically shifting 'K' elements towards the right.
The power of an array is defined as follows.
Power(k) = 0 * Ck[0] + 1 * Ck[1] + ... + (n - 1) * Ck[n - 1].
You have to find the maximum value among Power(0), Power(1), Power(2), ……., Power(n - 1).
Input Format
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains one integer ‘N’ denoting the number of elements in the array.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array 'ARR'.
Output Format:
For each test case, print a single line containing a single integer denoting the maximum power that can be obtained.
The output of each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10 ^ 4
0 <= ARR[i] <= 10 ^ 3
Where ‘T’ is the number of test cases, ‘N’ is the size of the given array, and ‘ARR[i]’ denotes the ith element of the array.
Time limit: 1 sec.
The idea here is to calculate the power of the array ARR every time by cyclically right shift the array ARR by 1, and then update the maximum power.
The algorithm is as follows:
- Declare a variable ans and set it to 0.
- Iterate from shift = 1 to N,
- Cyclically right shift the array ARR by 1.
- Declare a variable power and set it to 0.
- Iterate from j = 0 to N,
- Update power to power + (j * ARR[j]).
- Update ans to max(ans, power).
- Return the ans.
The idea is to calculate Power(k) using the value of Power(k-1) in constant time. The relation between Power(k) and Power(k-1) is as follows:
Power(k) = 0 * Ck[0] + 1 * Ck[1] + ... + (N-1) * Ck[N-1]
Power(k-1) = 0 * Ck-1[0] + 1 * Ck-1[1] + ... + (N-1) * Ck-1[N-1]
= 0 * Ck[1] + 1 * Ck[2] + ... + (N-2) * Ck[N-1] + (N-1) * Ck[0]
Then,
Power(k) - Power(k-1) = Ck[1] + Ck[2] + ... + Ck[N-1] + (1-N)*Ck[0]
= (Ck[0] + ... + Ck[N-1]) - N*Ck[0]
= sum - N*Ck[0]
Where, sum = (Ck[0] + ... + Ck[N-1]).
Thus,
Power(k) = Power(k-1) + sum - N*Ck[0].
k = 0, C[0] = ARR[0].
k = 1, C[0] = ARR[N - 1].
k = 2, C[0] = ARR[N - 2].
…
The algorithm is as follows:
- Declare a variable sum, and set it to 0.
- Declare a variable power, and set it to 0.
- Declare a variable prevPower, and set it to 0.
- Iterate from i = 0 to N,
- Update power to power + (i * ARR[i]).
- Update sum to sum + ARR[i].
- Update prevPower to power.
- Declare a variable ans and set it to power.
- Iterate from i = N - 1 to 1,
- Update power to prevPower + sum - (N * ARR[i]).
- Update ans to max(ans, power).
- Update prevPower to Power.
- Return ans.
