Right Rotate Using Cycles
JavaScript
Medium
4 views
Problem Description
Rotate array to the right by k steps, in-place idea using gcd cycles. Print rotated array.
Input Format
Line1: n k. Line2: n integers.
Output Format
One line: rotated array.
Official Solution
const fs=require('fs');const raw=fs.readFileSync(0,'utf8').trim();if(!raw)process.exit(0);const a=raw.split(/\\s+/);let i=0;const n=Number(a[i++]);let k=Number(a[i++]);let arr=new Array(n);for(let j=0;j<n;j++)arr[j]=a[i++];k%=n;if(k===0){process.stdout.write(arr.join(' '));process.exit(0);}const step=n-k;const gcd=(x,y)=>{while(y){[x,y]=[y,x%y];}return x;};const g=gcd(n,step);for(let s=0;s<g;s++){let cur=s;let prev=arr[s];while(true){let nxt=(cur+step)%n;if(nxt===s)break;const tmp=arr[nxt];arr[nxt]=prev;prev=tmp;cur=nxt;}arr[s]=prev;}process.stdout.write(arr.join(' '));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!