Rotate an array by k steps in c-CodePudding

We have given an array of n size and we to have to rotate it by k times where k can be greater than n in some cases .

My try -

#include<iostream>
using namespace std;

void inputarray(int arr[],int size){
    for(int i=0;i<size;i  ){
        cin>>arr[i];
    }
}


int main(){
    
    int n;
    cin>>n;
    int arr[100];

    inputarray(arr,n);

    int ansarr[n];

    int k;
    cin>>k;

    k = k%n;
    int j=0;

    for(int i =n-k;i<n;i  ){
        ansarr[j  ] = arr[i];
    }
    for(int i=0;i<=k;i  ){
        ansarr[j  ]=arr[i];
    }
    for(int i=0;i<n;i  ){
        cout<<ansarr[i];
    }

}

My output is coming correct for k>2 like my output for k=3 is -

6

1 2 3 4 5 6

3

456123

Which is correct but for k <2 like k = 2 , 1 and 0 my output is not coming correct . Like for K=2 my output is -

6

1 2 3 4 5 6

2

561234199699

So where am I doing wrong can anyone please tell .

CodePudding user response：

You can perform the rotation with a single loop, and this is completely bulletproof, using

for (int i= 0; i < n; i  )
{
   ans[i]= arr[(i   k) % n];
}

Now you can eliminate the modulo inside the loop by noting that i k remains in [0, n) for i in [- k, n - k), thus in [0, n - k), and i k - n remains in [0, n) for i in [n - k, 2n - k), thus in [n - k, n). So you can rewrite with two successive loops

k= k % n;
int i;
for (i= 0; i < n - k; i  )
{
   ans[i]= arr[i   k];
}
for (    ; i < n    ; i  )
{
   ans[i]= arr[i   k - n];
}

Caution: due to the behavior of the operator %, the above code will fail for k < 0.

CodePudding user response：

For starters pay attention to that variable length arrays like this

int ansarr[n];

are not a standard C feature. You should declare the array similarly to the array arr

int ansarr[100];

Or instead of arrays you could use standard container std::vector.

In any case your code is wrong at least because this for loop

for(int i =n-k;i<n;i  ){
    ansarr[j  ] = arr[i];
}

should start from i equal to k instead of i = n - k

for(int i = k;i<n;i  ){
    ansarr[j  ] = arr[i];
}

and correspondingly the second for loop should look like

for(int i=0;i < k;i  ){
    ansarr[j  ]=arr[i];
}

That is the condition of the loop should look like i < k.

Your program works for k equal to 3 because the expression n - k when n is equal to 6 yields the same value 3.

Bear in mind that there is standard algorithm std::reverse_copy declared in the header <algorithm> that you could use.

Here is a demonstration program

#include <iostream>
#include <algorithm>

int main()
{
    const size_t N = 6;
    for (size_t k = 0; k < N; k  )
    {
        int a[N] = { 1, 2, 3, 4, 5, 6 };
        int b[N];

        std::rotate_copy( a, a   k, a   N, b );

        std::cout << k << ":";

        for (size_t i = 0; i < N; i  )
        {
            std::cout << ' ' << b[i];
        }

        std::cout << '\n';
    }
}

The program output is

0: 1 2 3 4 5 6
1: 2 3 4 5 6 1
2: 3 4 5 6 1 2
3: 4 5 6 1 2 3
4: 5 6 1 2 3 4
5: 6 1 2 3 4 5

As for your approach with for loop then it is enough to use only one for loop. For example

#include <iostream>

int main()
{
    const size_t N = 6;
    for (size_t k = 0; k < N; k  )
    {
        int a[N] = { 1, 2, 3, 4, 5, 6 };
        int b[N];

        for (size_t j = 0, i = k; j < N; i = ( i   1 ) % N)
        {
            b[j  ] = a[i];
        }

        std::cout << k << ":";

        for (size_t i = 0; i < N; i  )
        {
            std::cout << ' ' << b[i];
        }

        std::cout << '\n';
    }
}

The program output is the same as shown above

0: 1 2 3 4 5 6
1: 2 3 4 5 6 1
2: 3 4 5 6 1 2
3: 4 5 6 1 2 3
4: 5 6 1 2 3 4
5: 6 1 2 3 4 5