Rotation of integers stored in an array

Question

I have made a simple program of rotation of integers in a given array.

#include <iostream>
using namespace std;

int main()
{
 int t;
 cin>>t;
 long i,j,n,k,l,m,x;
 long a[1000000];
 for(i=0;i<t;i++){
    cin>>n;
    cin>>k;
    for(j=0;j<n;j++){
        cin>>a[j];
    }
    for(m=0;m<k;m++){
        x=a[0];
        for(j=1;j<n;j++){
            x=a[j]+x;
            a[j]=x-a[j];
            x=x-a[j];
        }
        a[0]=x;
    }
    for(j=0;j<n;j++){
        cout<<a[j]<<" ";
    }
    cout<<endl;
 }
 return 0;
}

The question can be found here. My code processes the small inputs easily, but when the input reaches to the order of thousands it takes well over a second and it fails due to that. Any suggestions on how to solve this problem?

If you are to pursue a career that of a C++ developer then you are well advised to walk away from all those bogus online _programming competition_ sites. They spread toxic knowledge and you will not learn anything from them. Read C++ books instead. Here is a [nice list](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Ron, Aug 16 '17 at 21:07
Search your favorite C++ reference for [`std::rotate`](http://en.cppreference.com/w/cpp/algorithm/rotate). — Thomas Matthews, Aug 16 '17 at 21:09
@Scott Because OP was trying to adapt the array sizes accordingly? — user0042, Aug 16 '17 at 21:13
Take as input `1 1000000 1`. Think about how many steps your program will take to complete, and how you can improve that. Then do this for increasing values of `n`. — G. Sliepen, Aug 16 '17 at 21:13
Variable names like `long i,j,n,k,l,m,x`, though being syntactically correct, make a program very hard to read. I'd suggest to name variables after the role they play in your program, e.g. something like `nrOfRows`, `row`, ... — Stephan Lechner, Aug 16 '17 at 21:14
@user0042 I replaced that with dynamic allocation but that still does not help. — Upmanyu Tyagi, Aug 16 '17 at 21:14
@UpmanyuTyagi Use a `std::vector` instead. Though regarding the runtime you may have some other issues. — user0042, Aug 16 '17 at 21:16
If the problem being `exhausting stack` as @G.Sliepen said then you can allocate the array on the `heap` using `new`. — Raindrop7, Aug 16 '17 at 21:16
@Raindrop7 Sure. I'd never recommend anyone to use `new` unless that's absolutely necessary to apply for a solution (e.g. your own allocator implementations or such). — user0042, Aug 16 '17 at 21:20
@user0042: Yes that is it. but for some reasons for example for educational reason we can do that on our own. But since there are many facilities that C++ offers us we needn't to re-invent the wheel. — Raindrop7, Aug 16 '17 at 21:25

score 0 · Accepted Answer · answered Aug 17 '17 at 02:07

Some notes that can be used to speed things up:

Rotating by K, when K>N, is equivalent to rotating by K%N (as each rotation of N is an expensive no-op).
You don't actually need to generate the rotated array; you just need to print the values as they would appear in the rotated array.
In fact, you don't (necessarily) need to store all of the input in an array, but just the part that can't be printed until the last value in the array is read. (This would get the input and output intermingled if both were through the console, but not if at least one were a file.)

These can be used to turn your O(N^2) solution into an O(N) one.

Rotation of integers stored in an array

1 Answers1