CODEWITHSUNDEEP
javaarraysalgorithm
Matt
Matt

Reputation: 75

HackerRank Left Rotation in Java

I looked up the solution to this problem yesterday and tried to solve on my own today but found myself trying to solve this problem in a different way. I feel I may be overcomplicating the problem but I still want an answer to my possible solution just because it is bugging me to know (I am sure everyone has experienced this at some point or another). Anyway here is the problem: https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays

My idea is that you would first check to see if your array length was equal to the rotations you want then you would simply return the original. There is no work needed to be done.

My next idea would be to check to see if our rotations is greater than our array length. If this is the case, we can either do rotations - array length or ABS VALUE(array length - rotations), which gives us the same result. We can reassign this value to D.

Next, we can create a case to rotate right instead of left. When your rotation is greater than your array length / 2, then we would not to rotate left since we are doing extra work. We instead would want to rotate right. For example:

Array Length 4 Rotations 3 (LEFT)

We can simply rotate right once instead of rotating left 3 times. We could set the rotateRight boolean to true (otherwise set to false which indicated to rotateLeft as normal)

Anyway this is the part I get caught on. I am unsure of how to rotate my elements here. I was thinking of returning a new array. How can I get the correct values for my new array? I am facing issues with IndexOutOfBounds exceptions. Can I also use try catches in this example or is it overkill?

Here is the code I have currently it should match my thoughts from up above:

static int[] rotLeft(int[] a, int d) {
        int aLength = a.length;
        int counter = 0;
int[] newArray = new int[aLength];
        boolean rotateRight = false;
        if (aLength == d) {
            return a;
        }
        if (a.length - d < 0) {
            d = Math.abs(a.length - d);
        }

        if(d > a.length/2) {
            rotateRight = true;
        }
        
   
    return newArray;
    }

If you need any more info let me know.

Upvotes: 0

Views: 2632

Answers (1)

tucuxi
tucuxi

Reputation: 17945

There is little benefit to trying to simplify the maths, if it leads to a harder-to-write program -- especially since you do not want to rotate the array at all, and can simply place the correct values in the correct places directly.

If the old position of element i was i, after d left-rotations of an array of size len, its new position will be (i-d)%len. If d == len+1 this is indeed equivalent to (i+1)%len -- easier for humans, but computers calculate either expression just as happily.

So the suggested code is:

static int[] rotLeft(int[] a, int d) {
    int[] b = new int[a.length];
    for (int s=d, t=0; t<a.length; s++, t++) {
       // t is target position; s is source position
       b[t] = a[s%a.length];
    }
    return b;
}

Note: code is untested

Upvotes: 2

Related Questions