c++arraysvector

How can I calculate the minimum element-wise product of a right rotated array in c++?


Consider a one-dimensional array A of N integers. The element-place product of A is equal to Σ A [ k ] * k , i.e. it is the sum of the products formed when multiply each element of the array by its position. Eg, the element-position product of the array¨

A = [5, 3, 2, 6, 4, 1] is: 5 * 1 + 3 * 2 +2 * 3 + 6 * 4 + 4 * 5 + 1 * 6 = 67.

Rotating an array A by p positions (where 0 ≤ p < N) transforms A by taking its first p elements and putting them at the end. Eg, rotating A = [5, 3, 2, 6, 4, 1] by 2 places gives [2, 6, 4, 1, 5, 3].

I want to write a function in c++ that accepts A and N as parameters, and calculates the right rotation by p=1 of the array A with the minimum element-position product. The function should print the elements of array A after this rotation and return the corresponding product.

Example 1: (N = 6) A = [5, 3, 2, 6, 4, 1]

min_elem_pos_prod(A, N)

Output:

Product :64 Array: 6 4 1 5 3 2

iterations
p=0 :67 5 3 2 6 4 1
p=1 :76 3 2 6 4 1 5
p=2 :73 2 6 4 1 5 3
p=3 :64 6 4 1 5 3 2
p=4 :79 4 1 5 3 2 6
p=5 :82 1 5 3 2 6 4

I have function that right rotates a array :

#include <iostream>

void rotateRight(int arr[], int size) {
    int p = 1 ;
    int end = size - 1 ;
   
    for (int i = 0; i < p; i++) {
        int temp = arr[end];
        for (int j = end; j > 0; j--) {
            arr[j] = arr[j - 1];
         }
       arr[0] = temp;
    }
}

and the element wise product :

int elementWiseProduct(int arr[], int N) {
    int sum = 0; 
   
    for (int i = 0,j=1; i < N; ++i,j++) {
        sum += arr[i]*j;
    }
    return sum;
}

my question is how can I combine those two or some other function to output the needed result ?


Solution

  • Okay, so N-1 is the max amount of rotations you can do before getting our original array, so let us simply do this (and modify your rotateRight() method to accept p as parameter):

    // Calculate product without any rotation
    int product = elementWiseProduct(A, N);
    int numberOfRotations = 0;
    
    // Calculate product for all possible rotations
    // Replace values initialized above if product is smaller
    for (int i = 1; i <= N - 1; i++) {
        // Rotate once as your current implementation does
        rotateRight(A, N, 1);
        // Get the element-wise product of this rotation
        int newProduct = elementWiseProduct(A, N);
        if (newProduct < product) {
            product = newProduct;
            numberOfRotations = i;
        }
    }
    // Rotate array to get to the correct rotation
    // Rotation needed is one more since we need to cycle 
    // back to original array with one rotation
    rotateRight(A, N, numberOfRotations + 1);
    
    // Print array and minimum product
    ...