Rotation — Different Methods for Shifting Elements

Hey folks! Today, I'm writing a simple post to share some snippets about shifting vectors. I'm sharing this because I was working on a problem you can check it out here:1579B - Сортировка сдвигами and I came up with some ideas (you might know them already) to shift elements left and right. But I've gathered them in one place, so it can be like a handy guide for me or anyone else dealing with similar problems.

Let's dive into it!

When you need to shift a list a certain number of times, let's say k times, here's a simple way to make it easier:

First, calculate k % n, where n is the length of the vector. This gives you a smaller value that's still meaningful and will help simplify the process.

Now, depending on whether you're shifting to the left or to the right, there are two scenarios:

Shift Left: To shift elements to the left, follow these steps:

1. Move the element at index k + 1 to the beginning.
2. Shift the rest of the elements to their new positions.
3. Fill the space at the end with the first k elements.

(k = 2): - Original array: {1, 2, 3, 4, 5} - After left shift: {3, 4, 5, 1, 2}

So, let's take a look at how we can do this with some code examples using C++:

Shift Left

    vector<int> arr = {1, 2, 3, 4, 5};
    int n = arr.size(), k = 2,

    // Ensure k is less than n
    k %= n;

    vector<int> temp(n);

    // Shift left
    int j = 0;
    for (int i = k; i < n; ++i, ++j) {
        temp[j] = arr[i];
    }

    for (int i = 0; i < k; ++i, ++j) {
        temp[j] = arr[i];
    }

    // Display the shifted array
    for (int i : temp) {
        cout << i << ' '; // 3 4 5 1 2 
    }

Shift Right: Shifting elements to the right is a lot like left-shifting, but instead of using k, you would use n — k. Here's what you do:

1. Move the element at index n — k to the front.
2. Adjust the positions of the other elements accordingly.
3. Fill the gap at the end with the first n — k elements.

(k = 2): - Original array: {1, 2, 3, 4, 5} - After right shift: {4, 5, 1, 2, 3}

Shift Right

    vector<int> arr = {1, 2, 3, 4, 5};
    int n = arr.size(), k = 2;

    // Ensure k is less than n
    k %= n;

    vector<int> temp(n);

    // Shift right
    int j = 0;
    for (int i = n - k; i < n; ++i, ++j) {
        temp[j] = arr[i];
    }

    for (int i = 0; i < n - k; ++i, ++j) {
        temp[j] = arr[i];
    }

    // Display the shifted array
    for (int i : temp) {
        cout << i << ' '; // 4 5 1 2 3
    }

Shift Using Modulus

These implementations work, but I thought, "Can we make them even simpler?" That's when I discovered the magic of the remainder operation in making things easier.

Shift Left (Using Modulus)

    // Shift left with modulus
    for (int i = 0; i < n; ++i) {
        int newIndex = (i + k) % n;
        temp[newIndex] = arr[i];
    }

Shift Right (Using Modulus)

    // Shift right with modulus
    for (int i = 0; i < n; ++i) {
        int newIndex = (i - k + n) % n;
        temp[newIndex] = arr[i];
    }

Then, I thought about exploring if there's a built-in function that can shift the vector for you using the rotate function.

This function is available in the <algorithm.h> header file.

Using std::rotate for Shifting

rotate(start, middle, end);

Parameters

The rotate() function accepts the following parameters:

• start: The beginning of the range you want to rotate.

• middle: The element at which you want to start the rotation, making it the new beginning.

• end: The end of the range where you want the rotation to stop.

Shift left using std::rotate

    // Shift left using std::rotate
    rotate(arr.begin(), arr.begin() + k, arr.end());

Shift right using std::rotate

    // Shift right using std::rotate
    rotate(arr.begin(), arr.begin() + (n - k), arr.end());

Shift Right AGAIN

You can also shift elements right using std::rotate, use a reverse starting and ending point approach, similar to left shifting, but with rbegin() and rend():

    // Shift right using std::rotate
    rotate(arr.rbegin(), arr.rbegin() + k, arr.rend());

To sum it up, I prefer starting with manual solutions before diving into built-in functions. It makes coding smoother and more enjoyable for me. You can also solve the problem and then check how I approached the problem 218265509.

If you like these post, your positive comments motivate me to create more content like this in the future.