Rotate Function


  • 1
    J

    A array of size n is given with random number both positive and negative included.
    For example an array with n elements is defined as A_0,A_1.....A_n-1.
    Now f(0) is defined as sum of i*Ai.

    Rotate array by 1 clockwise
    f(1) as sum of i*Ai

    Rotate array by 1 again clockwise
    f(2) as sum of i*Ai.

    Find the f(n) which will be maximum of ( f(0), f(1).....f(n-1) ).

    Example
    Array [4,3,2,6]
    f(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 +18 = 25

    Rotate array by 1 i.e. [6,4,3,2] clockwise
    f(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 +6 + 6 = 16

    Rotate array by 1 again i.e. [2,6,4,3] clockwise
    f(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 +8 + 9 = 23

    Rotate array by 1 again i.e. [3,2,6,4] clockwise
    f(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

    So f(3) is the maximum

    So total number of rotation required is 3.


  • 0

    The brute force way is to simulate each of the steps by rotating array. And each time traverse the array once to update the maximum. Rotate array can be done in O(n), in-place.

    The complexity of the brute force method is O(n^2). Do you have a better method?


  • 0
    J

    @1337c0d3r Yes, there exist a method of O(n) complexity.
    Once you get f(0), just try to evaluate other f(i) from f(0).


  • 0

    Awesome! So it's similar to keeping a running sum, except you want to precompute the total sum first. Then use the total sum to calculate the next step.


  • 4

    This is the formula:

    S = A_0 + A_1 + ... + A_n-1

    Then,

    f(k) = f(k-1) + S - n*A_n-k.


  • 1
    J

    I think the formula should be
    f(k) = f(k-1) + S - n*A_n-k

    where k is 0 based


  • 0

    @jpsahoo14 Ahh, you are right! An off-by-one error... Just corrected it, thanks!


  • 4

    I came to the same solution as yours. Altough I it was tempting to have a look on the solution, I decide to try it myself at least 5 minutes and here is some code .

    int findRotateFunction(int[] nums) {
    	 int sum = 0;
    	 int f = 0;
    	 int n = nums.length;
    	 for (int index = 0; index < n; index++) {
    		 sum += nums[index];
    		 f += index * nums[index];
    	 }	
    	 int max= f;		
    	 for (int index = 1; index < n; index++) {			
    		 max = Math.max(max, f + sum - nums[n - index] * n);
    		 f += sum - nums[n - index] * n;
    	 }
    	 return max;
     }
    

  • 1

    @elmirap That's awesome! Working the problem out yourself is the best way to improve :100:


  • 0

    thank you @1337c0d3r


  • 0
    D

    we can make the problem a little bit harder by rotating k position clock-wise instead of 1?


  • 0
    R

    My solution:

    Consider the array [ A, B, C, D ] without rotating it but moving the coefficients:

    N = 4
    f(0) = 0A + 1B + 2C + 3D
    f(1) = 3A + 0B + 1C + 2D
    f(2) = 2A + 3B + 0C + 1D
    f(3) = 1A + 2B + 3C + 0D

    Observations:

    • at each step we remove A + B + C + D
    • at each step we add N * (arr[i])
    def maxF(nums):
       N = len(nums)
       simpleSum = sum(nums)
       best = val = sum(i * A for i, A in enumerate(nums))
       for i in range(0, N - 1):
          val += N * nums[i]
          val -= simpleSum
          best = max(best, val)
       return best
    

  • 0
    R

    @1337c0d3r Shouldn't the formula be f(k) = f(k-1) - S + n*A_n-k?


  • 0
    L

    @jpsahoo14

    Take an array nums=[A, B, C, D] for example, n=nums.length=4 and the f(0) to f(n-1) are as following:
    f(0) = 0A+1B+2C+3D
    f(1) = 1A+2B+3C+0D
    f(2) = 2A+3B+0C+1D
    f(3) = 3A+0B+1C+2D

    Given:
    f(1) - f(0) = A + B +C -3D = (A+B+C+D) -4D

    We got the results as below:
    f(1) = f(0) +(A+B+C+D) -4D
    f(2) = f(1) +(A+B+C+D) -4C
    f(3) = f(2) +(A+B+C+D) -4B

    So, the general formula is:

    • f(i) = f(i-1) + sum - n * nums[ n-i ]

  • 0
    M

    The idea of recursive function is awesome, there is another way to sort first ascending first and then compute the sum

    The idea is right because:
    After sorting, if A_i < A_j, i<j, if we exchange A_i and A_j, the sum will become smaller.

    Proof:
    iA_i+jA_j-iA_j-jA_i=(A_i-A_j)*(i-j) > 0.

    (


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.