Rotate Function - Leetcode Solution

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

1