Challenge 01: Rotating Arrays


Problem overview


A left rotation operation on an array of n size shifts each of the array's elements 1 unit to the left. For example, if 2 left rotations are performed on array [1, 2, 3, 4, 5], then the array would become [3, 4, 5, 1, 2].

Similarly, a right rotation operation on an array of n size shifts each of the array's elements 1 unit to the right. For example if 2 right rotations are performed on array [1, 2, 3, 4, 5], then the array would become [4, 5, 1, 2, 3].

Given an array of n integers, a number r, and a direction d (e.g L or R), perform r rotations on the n integers in the d direction and output the result as described below.

Inspiration

This problem is based on the Left Rotation challenge on HackerRank.

The intent is to challenge you to leverage a Sequence Container from CS140, such as the STL's std::vector, and its corresponding functionalities.

Input / Output

You will be given a series of inputs from standard input.

Each input array will consist of two lines:

  1. The first line consists of the n number of values, r number of rotations, and d rotational direction (L for left rotation and R for right rotation).

  2. The second line consists of the n elements in the array.

For each input array, you are to perform the specified r rotations in the d direction and print all the resulting array such that the elements are separated by spaces and the last element is followed by a newline character.

Example

Given the following input:

5 4 L
1 2 3 4 5
5 4 R
1 2 3 4 5

Your program should output the following:

5 1 2 3 4
2 3 4 5 1

Rubric

We will test your code using the following rubric:

+4    Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names
+3    No issues reported by valgrind on second test applied 
+18   Test cases successfully solved (1.5 points each)

HINT: The optimal solution for this challenge only uses a single for loop, and therefore is O(n). The key observation is not to perform r rotations, but rather think about the "offset," i.e., where a given element will be after the r rotations. Right rotations are a bit easier even though the test cases start with simple left rotations.

Testing your code prior to submission

To faciliate testing please clone the Github repository for this semester as follows:

git clone https://github.com/semrich/cs302-23.git cs302

Note that you will only have to initialize this repo once. You can update it throughout the semester by using:

git pull

We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type:

make test

Submission

To submit your solution, you must submit your solution.cpp a single archive on Canvas prior to the deadline.

Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!
You will receive a zero if it does not work/compile on hydra/tesla

Therefore, if you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline.