Leetcode Rotate Function problem solution

In this Leetcode Rotate Function problem solution 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.

Leetcode Rotate Function problem solution


Problem solution in Python.

class Solution:
    def maxRotateFunction(self, A: List[int]) -> int:
        list_len = len(A)
        
        # edge cases
        if list_len <= 1:
            return 0
        
        l_sum = 0
        l_times_n = [0] * list_len
        orig_sum = 0
        
        for i in range(list_len):
            val = A[i]
            l_sum += val
            l_times_n[i] = val*list_len
            orig_sum += val * i
        
        max_sum = orig_sum
        
        for i in range(list_len-1):
            orig_sum  = orig_sum - l_sum + l_times_n[i]
            if orig_sum >= max_sum:
                max_sum = orig_sum
        
        return max_sum



Problem solution in Java.

public class Solution {
    public int maxRotateFunction(int[] A) {
        int F = 0;
        int Asum = 0;
        int count = A.length;
        for (int i=0;i<count;i++){
            F+=A[i]*i;
            Asum+=A[i];
        }
        int max=F;
        for (int j=1;j<count;j++){
            F=F+Asum-A[count-j]*count;
            max=Math.max(max,F);
        }
        return max;
    }
}


Problem solution in C++.

class Solution {
public:
int maxRotateFunction(vector& nums) {

    int n=nums.size();
    int csum=0,m_sum=INT_MIN;
    int sum=accumulate(nums.begin(),nums.end(),0);
    for(int i=0;i<n;i++)
        csum+=(i*nums[i]);
    m_sum=max(csum,m_sum);
    for(int i=1;i<n;i++)
    {
        int t_sum=(csum-(nums[n-i]*(n-1)))+(sum-nums[n-i]);
        csum=t_sum;
        m_sum=max(csum,m_sum);
    }
return m_sum!=INT_MIN?m_sum:0;
}
};


Problem solution in C.

int maxRotateFunction(int* A, int ASize) {
    int i, last, sum,m;
    
    if(ASize<=1) return 0;
    
    last=0;
    sum=0;
    for(i=0;i<ASize;i++){
        last += A[i]*i;
        sum+=A[i];
    }
    m=last ;
    for(i=ASize-1;i>=1;i--){
        last += sum - (ASize*A[i]);
        if (last > m) m= last;
    }
    
    return m;
}


Post a Comment

0 Comments