Rotate Function

Posted: 18 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
Approach 1

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:

  1. Declare a variable ans and set it to 0.
  2. Iterate from shift = 1 to N,
    1. Cyclically right shift the array ARR by 1.
    2. Declare a variable power and set it to 0.
    3. Iterate from j = 0 to N,
      1. Update power to power + (j * ARR[j]).
    4. Update ans to max(ans, power).
  3. Return the ans.
Try Problem