CONCEPTS USED:

Basic Mathematics

DIFFICULTY LEVEL:

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.

SOLVING APPROACH:

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 ith 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 ith 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″]

Space Complexity: O(N), for creating Temporary Array to store results.
Previous post PERMUSEQ
Next post Min and Max

Leave a Reply

Your email address will not be published. Required fields are marked *