Solution For Rotate Function

Problem Statement:

You are given an integer array nums of length n. The Rotate Function is defined as follows:

• F(0) = 0 * nums[0] + 1 * nums[1] + … + (n – 1) * nums[n – 1]
• F(1) = 0 * nums[n – 1] + 1 * nums[0] + … + (n – 2) * nums[n – 2]
• F(2) = 0 * nums[n – 2] + 1 * nums[n – 1] + 2 * nums[0] + … + (n – 3) * nums[n – 3]
• …
• F(n-1) = (n – 1) * nums[0] + (n – 2) * nums[1] + … + 0 * nums[n – 1]

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

Example:

Input: nums = [4,3,2,6] Output: 26
Explanation:
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:

We can optimize the brute force approach here. Firstly, let’s write down the four equations shown in the example.

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

We can see that all the equations are quite similar. If we eliminate the first element, we can get a generic form, which is:

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

We can keep going and eventually get to a final equation, which is:

F(i) = F(i-1) – sum + n * nums[i-1]

where sum is the total sum of the previous array without i and n is the length of the nums array.

Now, all we need to do is iterate through the array and calculate the maximum value of F(i) for all i. We can first calculate the value of the sum of the original array, then use this sum to calculate the F values.

Here’s the Python solution for the problem:

def maxRotateFunction(nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
s = sum(nums)
F = sum([i * num for i, num in enumerate(nums)])
res = F
for i in range(1, n):
F = F + s – n * nums[n – i] res = max(res, F)
return res

Time Complexity: O(n)
Space Complexity: O(1)

The time complexity of the solution is O(n) and the space complexity of the solution is O(1).

Step by Step Implementation For Rotate Function

public int maxRotateFunction(int[] A) {
        if(A == null || A.length == 0){
            return 0;
        }
        int sum = 0;
        int len = A.length;
        int F = 0;
        for(int i = 0; i < len; i++){
            sum += A[i];
            F += i * A[i];
        }
        int max = F;
        for(int i = len - 1; i >= 1; i--){
            F = F + sum - len * A[i];
            max = Math.max(F, max);
        }
        return max;
    }

def rotateFunction(A):
    if len(A) <= 1:
        return 0
    sum_A = sum(A)
    F = [0] * len(A)
    for i in range(len(A)):
        for j in range(len(A)):
            F[i] += j * A[j]
    max_F = F[0]
    for i in range(1, len(A)):
        F[i] = F[i - 1] + sum_A - len(A) * A[len(A) - i]
        max_F = max(max_F, F[i])
    return max_F

// Solution: 

function rotateFunction(A) {
    
    // Base case: 
    if (A.length === 0) {
        return 0; 
    }
    
    // Initialize variables: 
    let sum = 0; 
    let f = 0; 
    
    // Loop through array to get sum and f(0): 
    for (let i = 0; i < A.length; i++) {
        sum += A[i]; 
        f += i * A[i]; 
    }
    
    // Initialize max variable: 
    let max = f; 
    
    // Loop through array again to get remaining f(i) values: 
    for (let i = 1; i < A.length; i++) {
        f = f + sum - A.length * A[A.length - i]; 
        max = Math.max(f, max); 
    }
    
    // Return max: 
    return max; 
}

int maxRotateFunction(vector& A) {
        int allSum = 0;
        int len = A.size();
        int F = 0;
        for (int i = 0; i < len; i++) {
                F += i * A[i];
                allSum += A[i];
        }
        int max = F;
        for (int i = len - 1; i >= 1; i--) {
                F = F + allSum - len * A[i];
                max = std::max(F, max);
        }
        return max;
}

public int MaxRotateFunction(int[] A) {
        if (A.Length == 0) {
            return 0;
        }
        int sum = 0;
        int F = 0;
        for (int i = 0; i < A.Length; i++) {
            sum += A[i];
            F += i * A[i];
        }
        int max = F;
        for (int i = A.Length - 1; i >= 1; i--) {
            F = F + sum - A.Length * A[i];
            max = Math.Max(F, max);
        }
        return max;
    }