We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Revisited this with an easier-on-the-eyes solution that finishes in O(n) time with O(n) memory.

functionmain(){// ...loopUntilAllSwapped(a,d);console.log(a.join(' ')+'\n');}/** * If a.length can be divided by d evenly, swapSeries will end * where it started without swapping all numbers. * This function ensures that all numbers are swapped. * * Variables: * a: array of numbers * d: number of left-rotations to perform * c: count of numbers swapped * i: index to start swapSeries() from */functionloopUntilAllSwapped(a,d){letc=0;leti=0;while(c<a.length){c+=swapSeries(a,i,d);i++;}}/** * Swaps elements in an array in-place. * * Variables: * a: array of numbers * i: index to start with * d: number of left-rotations to perform * c: count of numbers swapped, returned to loopUntilAllSwapped() * iS: index source (index of number to be moved) * iD: index destination (index iS will be moved to) * q: a queue that acts as a temporary buffer for numbers as they * move from source to destination * * Algorithm: * 1. Find index destination (iD) of a[iS] after d rotations to * left * 2. Place destination in temporary buffer (q). * 3. Replace destination with index source (iS) value (a[iS]). * 4. Repeat until we end where we started (iS === i) */functionswapSeries(a,i,d){letc=0;letiS=i;letq=[a[iS]];do{letiD=h(a.length,d,iS);q.push(a[iD]);a[iD]=q.shift();iS=iD;c++;}while(iS!==i);returnc;}/** * A constant-time formula to find index destination of i * after d rotations to left. */functionh(n,d,i){return((n-d%n)%n+i)%n;}

## Left Rotation

You are viewing a single comment's thread. Return to all comments →

Revisited this with an easier-on-the-eyes solution that finishes in O(n) time with O(n) memory.