We had to write a program that would perform rotation of elements in an array. The array size was entered by user, so it had to be in a sense, dynamic.Rotation or Circular ShiftingInitial Array: 1 3 7 4 8 6 5 2 9 Shift by: 4 Final Array: 6 5 2 9 1 3 7 4 8Notice, in rotation, each elements position increased by shift amount. Also, elements in the end came to the front.My TryI used an approach in which I had to create a new array of size = shift amount. This array stored the shift no. of elements in the end of array. Now I shifted all the elements in the beginning of array by shift amount. In the end, I copied the elements of shift sized array to beginning of original array. I tried to use minimum memory possible so only used shift sized array. I and keep it a bit fast (shift%=n statement to reduce inefficiency if shift >= n).// Rotation#include <iostream>int main() {    int n;    std::cout << Array size: ;    std::cin >> n;    int* list = new int[n];    std::cout << Enter elements:\n;    for( int i = 0; i < n; ++i) {        std::cin >> list[i];    }    int shift;    std::cout << Shift amount: ;    std::cin >> shift;    shift %= n; // to reduce work if shift > n    int* temp = new int[shift];    for( int i = n-shift; i < n ; ++i) {        temp[i-n+shift] = list[i];    }    for( int i = n-1; i >= shift; --i) {        list[i] = list[i-shift];    }    for( int i = 0; i < shift; ++i) {        list[i] = temp[i];    }    delete [] temp;    // Printing    for( int i = 0; i < n; ++i) {        std::cout << list[i] <<   ;    }    delete [] list;}QuestionMy question is that all the optimization that i was able to make were a bit obvious and natural. I wanted to know if there was a significant algorithmic, or memory optimization possible for this problem.PSI know there's a function std::rotate available from algorithm, but we had to solve this problem on our own.
Rotation of elements in an array
c++;performance;algorithm;memory optimization
I see some things that may help you improve your program.Separate I/O from calculationsThe program has three basic phases.  First, it gets input, then it manipulates that input, and then it produces output.  I would recommend putting the rotation code into a separate function.Consider signed vs. unsignedDoes it make sense to have a negative array size?  Does it make sense to have a negative shift value?  I'd answer no to the first and yes to the second question.  For that reason, I'd recommend making n a size_t or unsigned type and also adding code to handle negative rotations.Rethink your algorithmThe code currently creates a temporary array, but all that's really needed is a single temporary int.  Here's one way to do it:unsigned gcd(unsigned a, unsigned b) {    return b == 0 ? a : gcd(b, a % b);}void rotate(unsigned n, int shift, int *list) {    if (shift < 0) {        shift = n -(-shift % n);    } else {        shift %= n;    }    if (shift == 0) {        return;    }    for (unsigned cycles = gcd(n, shift); cycles; --cycles) {        unsigned i = 0;        unsigned nexti = n-shift;        for (int temp=list[nexti+cycles-1]; nexti; i = nexti) {            nexti = i+shift;            if (nexti >= n) {                nexti -= n;            }            std::swap(temp, list[i+cycles-1]);        }    }}Worked exampleThis is probably easier to understand with an example.  Let's start with a simple array or length 7 = { 0, 1, 2, 3, 4, 5, 6} and a requested shift amount of 4.  When the for loop starts we have this: