Rotate Function Problem

Problem

You are given an integer array nums of length n.

Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:

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

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

The test cases are generated so that the answer fits in a 32-bit integer.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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.

Example 2:

1
2
3
4

Input:
nums = [100]
Output:
 0

Solution

Method 1 – Mathematical Formula (Iterative)

Intuition

Instead of recalculating F(k) for each rotation, we use a formula to compute F(k) from F(k-1) efficiently. The difference between F(k) and F(k-1) is related to the sum of nums and the last element moved to the front.

Approach

  1. Compute F(0) and the sum of nums.
  2. For each k from 1 to n-1:
    • F(k) = F(k-1) + sum(nums) - n * nums[n-k]
  3. Track the maximum value of F(k).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int maxRotateFunction(vector<int>& nums) {
        int n = nums.size();
        long sum = 0, f = 0, ans = INT_MIN;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            f += i * nums[i];
        }
        ans = f;
        for (int k = 1; k < n; ++k) {
            f = f + sum - n * nums[n - k];
            ans = max(ans, f);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func maxRotateFunction(nums []int) int {
    n := len(nums)
    sum, f := 0, 0
    for i, x := range nums {
        sum += x
        f += i * x
    }
    ans := f
    for k := 1; k < n; k++ {
        f = f + sum - n*nums[n-k]
        if f > ans {
            ans = f
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxRotateFunction(int[] nums) {
        int n = nums.length;
        long sum = 0, f = 0, ans;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            f += (long)i * nums[i];
        }
        ans = f;
        for (int k = 1; k < n; ++k) {
            f = f + sum - n * nums[n - k];
            ans = Math.max(ans, f);
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun maxRotateFunction(nums: IntArray): Int {
        val n = nums.size
        var sum = 0L
        var f = 0L
        for (i in nums.indices) {
            sum += nums[i]
            f += i * nums[i].toLong()
        }
        var ans = f
        for (k in 1 until n) {
            f = f + sum - n * nums[n - k]
            ans = maxOf(ans, f)
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def maxRotateFunction(self, nums: list[int]) -> int:
        n = len(nums)
        s = sum(nums)
        f = sum(i * x for i, x in enumerate(nums))
        ans = f
        for k in range(1, n):
            f = f + s - n * nums[n - k]
            ans = max(ans, f)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn max_rotate_function(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let sum: i32 = nums.iter().sum();
        let mut f: i32 = nums.iter().enumerate().map(|(i, &x)| i as i32 * x).sum();
        let mut ans = f;
        for k in 1..n {
            f = f + sum - n as i32 * nums[n - k];
            ans = ans.max(f);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    maxRotateFunction(nums: number[]): number {
        const n = nums.length
        let sum = nums.reduce((a, b) => a + b, 0)
        let f = nums.reduce((a, x, i) => a + i * x, 0)
        let ans = f
        for (let k = 1; k < n; ++k) {
            f = f + sum - n * nums[n - k]
            ans = Math.max(ans, f)
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass for sum and iterative formula.
  • 🧺 Space complexity: O(1) — Only a few variables used.