Rotate Function

Moderate
0/80
Average time to solve is 25m
2 upvotes
Asked in companies
AppleMicrosoftGoogle inc

Problem statement

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).

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
4 
4 3 2 6
2
9 1
Sample Output 1:
26
9
Explanation for Sample Input 1:
For the first test case, 
Power(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25 
Power(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16 
Power(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23 
Power(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So, the maximum power is 26.

For the second test case, 
Power(0) = (0 * 9) + (1 * 1) = 1
Power(1) = (0 * 1) + (1 * 9) = 9
So, the maximum power is 9.
Sample Input 2:
2
7
9 2 3 5 0 7 2
1
5
Sample Output 2:
105
0
Hint

Try to calculate the power of the array for each cyclic rotation from 1 to N?

Approaches (2)
Brute force

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.
Time Complexity

O(N * N), where N is the size of the given array.

 

Here, we are just iterating over input array ARR for every right shift by 1, which is of order N * N. Hence, the overall time complexity is O(N * N).

Space Complexity

O(1).

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Rotate Function
Full screen
Console