CODEWITHSUNDEEP
javascriptarraysalgorithm
Funny Tiger
Funny Tiger

Reputation: 11

What's wrong with my array rotation algorithm?

I was working on Codility on a challenge to rotate an array k times. I came up with this solution which in theory should work but in reality only got a 25% score.

Problem Statement

zero-indexed array A consisting of N integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is also moved to the first place.

For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7]. The goal is to rotate array A K times; that is, each element of A will be shifted to the right by K indexes.

Write a function:

function solution(A, K);

that, given a zero-indexed array A consisting of N integers and an integer K, returns the array A rotated K times.

For example, given array A = [3, 8, 9, 7, 6] and K = 3, the function should return [9, 7, 6, 3, 8].

Assume that:

•N and K are integers within the range [0..100]; •each element of array A is an integer within the range [−1,000..1,000].

function solution(A, K) {
    for (var i = 1; i < K; i++) {
        A.push(A.shift());
    }
    return A;
}

Variable A represents an array, and variable K represents the number of rotations needed.

To add an element to the end of an array, the push function is used. Whereas the shift function removes the first element of an array. This seems like what a rotation would be.

** Test Results**

empty-array: passed

single: One element (0 <= k <= 5): Passed

double: Two elements (k <= n): Failed

small1: Failed

small2: Failed

maximal: Maximal n and k: Failed

Upvotes: 0

Views: 598

Answers (3)

James Ray
James Ray

Reputation: 474

Some slight modifications to @ie_m's solution (using uppercase and solution to keep Codility happy, and just returning the array if K mod A.length == 0):

function solution(A, K) {
    K %= A.length;
    if (K === 0) {
        return A;
    } else {
        return A.slice(-K).concat(A.slice(0, -K));
    }
}

Upvotes: 0

le_m
le_m

Reputation: 20228

You have two mistakes in your code:

  • Your loop executes only K-1 times, thus shifting the array only K-1 instead of K times
  • You shift to the left, but the requirements state you should shift to the right.

How to fix this?

  • start your loop from i = 0 instead of i = 1 to shift K times
  • Use unshift and pop instead of push and shift to reverse the direction.

Your fixed code:

function solution(A, K) {
    for (var i = 0; i < K; i++) {
        A.unshift(A.pop());
    }
    return A;
}

A "real-world" solution would probably look as follows:

function rotateRight(a, k) {
    k %= a.length;
    return a.slice(-k).concat(a.slice(0, -k));
}

Upvotes: 1

Paul
Paul

Reputation: 141829

When K is 1 your loop isn't entered. When K is 2 your loop iterates once instead of twice. I would change the var i = 1 to var i = 0 to make it iterate K times, but you could also change the < K to <= K if you prefer.

Upvotes: 1

Related Questions