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.

Solid answer.
I would like to point out to people that this does require double the memory of the intial answer as this requires a second array to store all the properly ordered array.
If you're on a memory tight situation, this would not be a favorable solution.

To solve this, I've shifted the elements in the array in O(n) time and O(n) memory (vs O(2n)). Not as easy on the eyes, though :(

functionprocessData(input){// get `n` and `d` from inputconstlines=input.split('\n');constfirstLine=lines[0].split(' ').map(Number);constn=firstLine[0];constd=firstLine[1];// process each linelines.slice(1,lines.length).forEach(line=>{// no need to shift in these casesif(n===1||d===n){console.info(line);}else{// shift digitsconsta=line.split(' ').map(Number);letlastLastItem=null;letcount=0;leti=0;while(count<n){i++;conststart=i;letj=start;do{count++;letlastItem=lastLastItem;lastLastItem=a[j];a[j]=lastItem;j=shiftLeft(n,d,j);}while(j!==start);a[start]=lastLastItem;}console.info(a.reduce((acc,value)=>{returnacc+' '+value;}));}});}/** * @param {Number} n total number of elements * @param {Number} d number of shifts to left * @param {Number} i index to begin shifting from * @returns {Number} new index after shifting to left */functionshiftLeft(n,d,i){return(n-d+i)%n;}

I'm ignoring the processing time on input string manipulation and such. This examples assumes they gave us an existing array to manipulate.

Hey! Could you include comments in your code please? I use C and dont kow other language as of now but would like to learn from your solution O(n) is preety nice

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;}

YOU don't need second vector for this. Just store the 0th index of a vector in some temp variable and when the whole array gets shifted by one left rotation ,store it at the n-1th index. Repeat the process till d becomes zero.

## Left Rotation

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

Solid answer. I would like to point out to people that this does require double the memory of the intial answer as this requires a second array to store all the properly ordered array. If you're on a memory tight situation, this would not be a favorable solution.

To solve this, I've shifted the elements in the array in O(n) time and O(n) memory (vs O(2n)). Not as easy on the eyes, though :(

I'm ignoring the processing time on input string manipulation and such. This examples assumes they gave us an existing array to manipulate.

Hey! Could you include comments in your code please? I use C and dont kow other language as of now but would like to learn from your solution O(n) is preety nice

i think your solutions is O(n^2) for the worst case.

It looks like it, because of the nested loops. But it'll break out of all loops after

`n`

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

YOU don't need second vector for this. Just store the 0th index of a vector in some temp variable and when the whole array gets shifted by one left rotation ,store it at the n-1th index. Repeat the process till d becomes zero.