# Array Rotation

#### CONCEPTS USED:

Basic Mathematics

Medium

#### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

With a given array of size `N` and steps `K`, we have to print the array after `K` rotations to the right.

See original problem statement here

#### For Example:

``````Input:

N = 5, K = 2
A[] = [1, 2, 3, 4, 5]

Output:

[4, 5, 1, 2, 3]

Explanation:

We are supposed to right rotate the array by 2 steps, so each element is shifted to the right by 2 places and elements at the end of the array will be shifted to the starting indexes of the array in a fashion similar to circular arrays.  ``````

NOTE : Don’t forget to `K` = `K` % `N`, as `K` can be greater than `N`.

#### BRUTE FORCE METHOD

1. “Naive solution would be to shift the array `K` times one by one according to data structures in c++.

2. Write a function that shifts all the elements by one place to the right.

3. Run a loop `K` times and execute this function.

4. `Time Complexity` of this solution will be `O(K*N)`.

#### SOLUTIONS:

[TABS_R id=651]

Time Complexity: `O(N`*`K)`

Space Complexity: `O(1)`

#### EFFICIENT METHOD:

1. Each and every element is shifting towards right by a given step number.

2. This implies that an element sitting at `i`th position will be shifted to `(i+k)^{th}` position or in other words the element sitting at the `(i-k)^{th}` position will come to the `i`th position.

3. But remember one thing adding current index value to the step number may result in pointing to a number that is greater than the array length or an array out of bound exception may occur.

4. For this scenario, we will take modulus of the obtained number i.e. `(i+k)`%`N` with the array length so that it will remain in the valid array locations.

5. For current location, element present at the `(i-k+N)`%`N` will be shifted to the current location.

6. `N` is additionally added to the formula in order to avoid modulus of negative number. But the result would be similar.

#### SOLUTIONS:

[TABS_R id=652]
[forminator_quiz id=”686″]