Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

Solution

To me it is easier to see the solution if you leave the array as is and rotate the factors left (same result as rotating array right).

For simplicity take an array with 4 elements
[a,b,c,d]

f(0) = 0a + 1b + 2c +3d
f(1) = 3a + 0b + 1c +2d
f(2) = 2a + 3b + 0c +1d
f(3) = 1a + 2b + 3c +0d

Now look what happens when you take difference between f(k) – f(k-1)
f(1) – f(0) = 3a – b – c – d = 4a – (a + b + c + d) = length * a – sum
f(2) – f(1) = -a + 3b – c – d = 4b – (a + b + c + d) = length * b – sum
f(3) – f(2) = -a – b +3c – d = 4c – (a + b + c + d) = length * c – sum

You can see if you calculate (manually) f(0) you can get f(1) by adding length * a and subtracting the sum.

So initially you need to compute the sum and f(0) then just iterate through and get the value of f(i) for each i and record the max.

Hope that helps!

Program

class Solution {
    public int maxRotateFunction(int[] A) {
        int sumA  = 0;
        int prevRotationSum = 0;
        for(int i=0;i<A.length;i++)
        {
            sumA += A[i];
            prevRotationSum += i*A[i];
        }
        
        int len = A.length;
        int max = prevRotationSum;
        for(int i=A.length-1;i>0;i--)
        {
            prevRotationSum = prevRotationSum + sumA - len * A[i];
            max = Math.max(max,prevRotationSum);
        }
        return max;
    }
}

Code Walkthrough

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

 for (int i = 0; i < A.length; i++) {
            sumA += A[i];
            prevRotationSum += i * A[i];
        }

sumA = 15;
prevRotationSum = 25;

A = [4, 3, 2, 6]

int len = A.Length; //4

for(int i=len-1;i>0;i--)
{
   //i runs from 3, 2, 1

   //i = 3 
   prevRotationSum  = prevRotationSum + sumA - len * A[i];
   prevRotationSum  = 25 + 15 - 4 * 6 = 40 - 24 = 16;

   //i = 2
   prevRotationSum  = prevRotationSum + sumA - len * A[i];
   prevRotationSum = 16 + 15 - 4 * 2 = 23
   
   //i = 1
   prevRotationSum  = prevRotationSum + sumA - len * A[i];
   prevRotationSum  = 23 + 15 - 4 * 3 = 26

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s