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
...

``````