Today, I took on the Left Rotation challenge on HackerRank's Array section using C++. This challenge took me a lot of thinking to complete. I will explain my thinking process below.
My first thought before starting this assignment is that if I rotate every value in the array to the left one by one, it may take a significant amount of time if I encounter a test case with a big array. To combat this, what I'll want to do is move every value to their final destination instead of moving them one by one to their final destination.
To accomplish this, first I considered recursion. However, recursion proved a little too difficult to think about doing because I had several variables I wanted to use, and those variables would be altered in some way through the iterations of the recursion.
My next thought is to have a for loop going through a counter. This counter makes sure every value in the array is rotated. I instantiated two temporary integer variables that will hold the value at the beginning and the value at the destination. A place integer variable kept track of where I was in the array. Through the iterations of the counter for loop, I will be working from the place from the previous iteration.
My first challenge is finding out how to make this work when the first thing I want to do will be different from every iteration after it. To solve this, I made an if statement that said if the counter variable is equal to zero, meaning this is the for loop's first iteration, then I will make the temporary variable equal to the value at place, which should be the value at the first index. I did not have to make an else statement or add any additional stuff into the if statement because I found out that was the only significant difference between the first iteration and every one after.
I already knew how the rotation will be done. I will subtract the d variable from the place variable. If place is less than zero, then I will make place equal to the size of the array minus the place variable's value.
My next challenge was finding out how to swap. Initially, I swapped the value at the original location with the value at the final destination. However, the challenge was that because of how my code was done, the value at the final destination is never visited again at the previous place and so is never put at its final destination. It is only the value that is at the final destination that keeps being rotated. On top of that, I never stored the value that I would be rotating for its next iteration. To fix this problem, instead of swapping, I just stored the variable in a second temporary variable as mentioned previously and did not do anything with the value at the previous place. I only focused on changing the value at the new place.
My next challenge was finding out what to do with one of the test cases. One test case was 10 left rotations with an array of size 20. The issue was that my for loop only every changed the values at the first place, the last place, and the middle place because after two 10-left-rotations, I ended up back at the origin. To solve this, I made an origin variable that kept track of if my for loop ever got back to origin. I made an if statement that said if place is equal to origin and counter is not equal to the size of the array minus 1, or the last iteration, then add one to place and origin, and make the temporary variable equal to the value at the new place. I put this at the end of the for loop so that first the steps inside the for loop will be completed, and then the variables I mentioned will be changed for the next iteration.
I hope to discuss more about other challenging HackerRank challenges in future posts. I will use C++ to do the challenges in preparation of my internship.
Top comments (0)