Given non-negative integers K, M, and an array arr[ ] consisting of N elements, the task is to find the Mth element of the array after K right rotations.
Examples:
Input: arr[] = {3, 4, 5, 23}, K = 2, M = 1
Output: 5
Explanation:
The array after first right rotation a1[ ] = {23, 3, 4, 5}
The array after second right rotation a2[ ] = {5, 23, 3, 4}
1st element after 2 right rotations is 5.
Input: arr[] = {1, 2, 3, 4, 5}, K = 3, M = 2
Output: 4
Explanation:
The array after 3 right rotations has 4 at its second position.
Naive Approach:
The simplest approach to solve the problem is to Perform Right Rotation operation K times and then find the Mth element of the final array.
Algorithm:
- Define a function named leftrotate that takes a reference to a vector of integers v and an integer d as input parameters.
- Reverse the first d elements of the vector v.
- Reverse the remaining elements of the vector v starting from index d to the end.
- Reverse the entire vector v.
- Define a function named rightrotate that takes a reference to a vector of integers v and an integer d as input parameters.
- Call the leftrotate function with the vector v and the length of the vector minus d as input parameters.
- Define a function named getFirstElement that takes an array of integers a, its size N, an integer K and an integer M as input parameters.
- Declare a vector of integers v.
- Add all the elements of the array a to the vector v.
- Loop K times.
- Call the rightrotate function with the vector v and 1 as input parameters.
- Return the Mth element of the vector v minus 1 as the output of the function.
- In the main function, define an array of integers a, its size N, an integer K, and an integer M.
- Initialize the values of the array a, N, K, and M.
- Call the getFirstElement function with the array a, N, K, and M as input parameters and print its output.
Below is the implementation of the approach:
Javascript
// JavaScript program to find the Mth element// of the array after K right rotations.// Function to left rotate the array by dfunction leftrotate(arr, d) { arr.push.apply(arr, arr.splice(0, d));}// Function to right rotate the array by dfunction rightrotate(arr, d) { leftrotate(arr, arr.length - d);}// Function to return Mth element of// array after K right rotationsfunction getFirstElement(arr, N, K, M) { let v = []; for (let i = 0; i < N; i++) v.push(arr[i]); // Right rotate K times while (K--) { rightrotate(v, 1); } // return Mth element return v[M - 1];}// Driver codelet a = [ 1, 2, 3, 4, 5 ];let N = a.length;let K = 3, M = 2;// Function callconsole.log(getFirstElement(a, N, K, M)); |
Output
4
Time Complexity: O(N * K)
Auxiliary Space: O(N)
Efficient Approach:
To optimize the problem, the following observations need to be made:
- If the array is rotated N times it returns the initial array again.
For example, a[ ] = {1, 2, 3, 4, 5}, K=5
Modified array after 5 right rotation a5[ ] = {1, 2, 3, 4, 5}.
- Therefore, the elements in the array after Kth rotation is the same as the element at index K%N in the original array.
- If K >= M, the Mth element of the array after K right rotations is
{ (N-K) + (M-1) } th element in the original array.
- If K < M, the Mth element of the array after K right rotations is:
(M – K – 1) th element in the original array.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Function to return Mth element of// array after k right rotationsint getFirstElement(int a[], int N, int K, int M){ // The array comes to original state // after N rotations K %= N; int index; // If K is greater or equal to M if (K >= M) // Mth element after k right // rotations is (N-K)+(M-1) th // element of the array index = (N - K) + (M - 1); // Otherwise else // (M - K - 1) th element // of the array index = (M - K - 1); int result = a[index]; // Return the result return result;}int main(){ int a[] = { 1, 2, 3, 4, 5 }; int N = 5; int K = 3, M = 2; cout << getFirstElement(a, N, K, M); return 0;}// This code is contributed by nmkiniqw7b. |
Java
// Java program to implement// the above approachclass GFG { // Function to return Mth element of // array after k right rotations static int getFirstElement(int a[], int N, int K, int M) { // The array comes to original state // after N rotations K %= N; int index; // If K is greater or equal to M if (K >= M) // Mth element after k right // rotations is (N-K)+(M-1) th // element of the array index = (N - K) + (M - 1); // Otherwise else // (M - K - 1) th element // of the array index = (M - K - 1); int result = a[index]; // Return the result return result; } // Driver Code public static void main(String[] args) { int a[] = { 1, 2, 3, 4, 5 }; int N = 5; int K = 3, M = 2; System.out.println(getFirstElement(a, N, K, M)); }}// This code is contributed by nmkiniqw7b. |
Python
# python program to implement# the above approach# Function to return Mth element of# array after k right rotationsdef getFirstElement(a, N, K, M): # The array comes to original state # after N rotations K %= N # If K is greater or equal to M if(K >= M): # Mth element after k right rotations index = (N - K) + (M - 1) # otherwise else: # (M - K - 1) th element # of the array index = (M - K - 1) result = a[index] return result# driver codea = [1, 2, 3, 4, 5]N = 5K = 3M = 2print(getFirstElement(a, N, K, M))# This code is contributed by nmkiniqw7b. |
Javascript
<script>// JavaScript program to implement // the approach// Function to return Mth element of// array after k right rotationsfunction getFirstElement(a, N, K, M){ // The array comes to original state // after N rotations K %= N; let index; // If K is greater or equal to M if (K >= M) // Mth element after k right // rotations is (N-K)+(M-1) th // element of the array index = (N - K) + (M - 1); // Otherwise else // (M - K - 1) th element // of the array index = (M - K - 1); let result = a[index]; // Return the result return result;} // Driver Code let a = [ 1, 2, 3, 4, 5 ]; let N = 5; let K = 3, M = 2; document.write(getFirstElement(a, N, K, M)); </script> |
C#
// C# program to implement// the above approachusing System;public class GFG{ // Function to return Mth element of // array after k right rotations public static int GetFirstElement(int[] a, int N, int K, int M) { // The array comes to original state // after N rotations K %= N; int index; // If K is greater or equal to M if (K >= M) { // Mth element after k right // rotations is (N-K)+(M-1) th // element of the array index = (N - K) + (M - 1); } else { // (M - K - 1) th element // of the array index = (M - K - 1); } int result = a[index]; // Return the result return result; } public static void Main() { int[] a = { 1, 2, 3, 4, 5 }; int N = 5; int K = 3; int M = 2; Console.WriteLine(GetFirstElement(a, N, K, M)); }} |
Output:
4
Time complexity: O(1)
Auxiliary Space: O(1)
Please refer complete article on Mth element after K Right Rotations of an Array for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
