• + 0 comments

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

    function main() {
      	// ...
        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
     */
    function loopUntilAllSwapped(a, d) {
        let c = 0;
        let i = 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) 
     */
    function swapSeries(a, i, d) {
        let c=0;
        let iS = i;
        let q = [a[iS]];
        do {
            let iD = h(a.length, d, iS);
            q.push(a[iD]);
            a[iD] = q.shift();
            iS = iD;
            c++;
        } while (iS !== i);
        return c;
    }
    
    /**
     * A constant-time formula to find index destination of i 
     * after d rotations to left.
     */
    function h(n, d, i) {
        return ((n-d%n)%n+i)%n;
    }