Leetcode 396. Rotate Function
Problem Explanation
The main task of this problem is to figure out the maximum value that can be obtained by rotating an array of integers in a given function. Assume that there is an array 'A' and 'n' is the length of the array. After rotating the array 'A' k positions clock-wise, we get another array 'Bk'. The rotation function 'F' is defined as F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1]. We need to calculate the maximum value of F(0), F(1), ..., F(n-1).
If we look at the function itself, we can observe that each rotation will shift all numbers right by one position. Therefore, the sum of products of number and index will be sum + n*Bk[0]. We need to calculate the rotation function for each possible rotation and keep track of the maximum one.
Solution Approach
The basic idea of the solution is to find a relationship between each round of rotation to accumulate the result for each round by only adding the difference between each round.
First, we calculate the total sum and the initial rotation function. Then, for each new rotation, we update the rotation function by adding the total sum of the array and subtracting the size of the array times the element that gets out of the array after the rotation. We keep track of the maximum rotation function value.
In other words, after rotating, every number contributes its value to the new result. However, the number that is kicked out of the array will not contribute its value, but will decrease the total sum times its count, times array length. Therefore, each time we rotate, we just add the whole sum, but deduct "size times the last element" from it.
Let's go through an example: Suppose we have an array [4, 3, 2, 6] F(0) = (04) + (13) + (22) + (36) = 25 To calculate F(1), we will add total sum to F(0) and then subtract the product of last element and size of array.
That will be F(1) = F(0) + sum([4,3,2,6]) - 4*6 = 25 + 15 - 24 = 16 Similarly, we calculate F(2) and F(3) to find the maximum from all rotations which in this case would be 26.
1 2 python 3class Solution: 4 def maxRotateFunction(self, nums): 5 total = sum(nums) 6 rotation_function = sum(i * nums[i] for i in range(len(nums))) 7 max_value = rotation_function 8 for i in range(1, len(nums)): 9 rotation_function += total - len(nums) * nums[-i] 10 max_value = max(max_value, rotation_function) 11 return max_value
Python Solution
1 2 python 3class Solution: 4 def maxRotateFunction(self, nums): 5 total = sum(nums) 6 rotation_function = sum(i * nums[i] for i in range(len(nums))) 7 max_value = rotation_function 8 for i in range(1, len(nums)): 9 rotation_function += total - len(nums) * nums[-i] 10 max_value = max(max_value, rotation_function) 11 return max_value
Java Solution
1 2 java 3class Solution { 4 public int maxRotateFunction(int[] nums) { 5 int sum = 0, rotation = 0; 6 for (int i = 0; i < nums.length; i++) { 7 sum += nums[i]; 8 rotation += i * nums[i]; 9 } 10 int max_value = rotation; 11 for (int i = 1; i < nums.length; i++) { 12 rotation += sum - nums.length * nums[nums.length - i]; 13 max_value = Math.max(max_value, rotation); 14 } 15 return max_value; 16 } 17}
Javascript Solution
1 2 javascript 3class Solution { 4 maxRotateFunction(nums) { 5 let sum = 0, rotation = 0; 6 for (let i = 0; i < nums.length; i++) { 7 sum += nums[i]; 8 rotation += i * nums[i]; 9 } 10 let max_value = rotation; 11 for (let i = 1; i < nums.length; i++) { 12 rotation += sum - nums.length * nums[nums.length - i]; 13 max_value = Math.max(max_value, rotation); 14 } 15 return max_value; 16 } 17}
C++ Solution
1 2 c++ 3class Solution { 4public: 5 int maxRotateFunction(vector<int>& nums) { 6 int sum = 0, rotation = 0; 7 for (int i = 0; i < nums.size(); i++) { 8 sum += nums[i]; 9 rotation += i * nums[i]; 10 } 11 int max_value = rotation; 12 for (int i = 1; i < nums.size(); i++) { 13 rotation += sum - nums.size() * nums[nums.size() - i]; 14 max_value = max(max_value, rotation); 15 } 16 return max_value; 17 } 18};
C# Solution
1 2 csharp 3public class Solution { 4 public int MaxRotateFunction(int[] nums) { 5 int sum = 0, rotation = 0; 6 for (int i = 0; i < nums.Length; i++) { 7 sum += nums[i]; 8 rotation += i * nums[i]; 9 } 10 int max_value = rotation; 11 for (int i = 1; i < nums.Length; i++) { 12 rotation += sum - nums.Length * nums[nums.Length - i]; 13 max_value = Math.Max(max_value, rotation); 14 } 15 return max_value; 16 } 17}
Ruby Solution
1 2 ruby 3class Solution 4 def max_rotate_function(nums) 5 total = nums.sum() 6 rotation = 0 7 for i in 0...nums.length() 8 rotation += i * nums[i] 9 end 10 max_value = rotation 11 for i in 1...nums.length() 12 rotation += total - nums.length() * nums[-i] 13 max_value = [max_value, rotation].max() 14 end 15 return max_value 16 end 17end
Swift Solution
1 2 swift 3class Solution { 4 func maxRotateFunction(_ nums: [Int]) -> Int { 5 let total = nums.reduce(0, +) 6 var rotation = 0 7 for i in 0..<nums.count { 8 rotation += i*nums[i] 9 } 10 var max_value = rotation 11 for i in 1..<nums.count { 12 rotation += total - nums.count * nums[nums.count - i] 13 max_value = max(max_value, rotation) 14 } 15 return max_value 16 } 17}
Kotlin Solution
1
2 kotlin
3class Solution {
4 fun maxRotateFunction(nums: IntArray): Int {
5 var total = 0
6 var rotation = 0
7 for (i in nums.indices) {
8 total += nums[i]
9 rotation += i * nums[i]
10 }
11 var max_value = rotation
12 for (i in 1 until nums.size) {
13 rotation += total - nums.size * nums[nums.size - i]
14 max_value = max_value.coerceAtLeast(rotation)
15 }
16 return max_value
17 }
18}
In conclusion, this problem is a good example of how to optimize a brute force solution by identifying patterns or relationships between sub-problems. The key is to understand the rotation operation and its effects on the array and the given function. This enhances algorithmic thinking and helps in solving problems more efficiently.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.