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 called leftrotate that takes a vector and an integer d as input. The function should reverse the elements of the vector from the beginning up to index d, then from index d to the end, and finally the entire vector.
- Define a function called rightrotate that takes a vector and an integer d as input. The function should call leftrotate with the vector and the difference between the size of the vector and d as arguments.
- Define a function called getFirstElement that takes an integer array a, its size N, and two integers K and M as input. The function should do the following:
- Initialize a vector v with the elements of array a.
- Right rotate the vector v K times by calling rightrotate in a loop with v and the integer value 1 as arguments, K times.
- Return the Mth element of the rotated vector v.
- In the main function, initialize an integer array a and its size N, and two integers K and M with appropriate values.
- Call the function getFirstElement with an array a, N, K, and M as arguments and print the returned value.
Below is the implementation of the approach:
C++
// C++ program to find the Mth element// of the array after K right rotations.#include <bits/stdc++.h>using namespace std;// In-place rotates s towards left by dvoid leftrotate(vector<int>& v, int d){ reverse(v.begin(), v.begin() + d); reverse(v.begin() + d, v.end()); reverse(v.begin(), v.end());}// In-place rotates s towards right by dvoid rightrotate(vector<int>& v, int d){ leftrotate(v, v.size() - d);}// Function to return Mth element of// array after k right rotationsint getFirstElement(int a[], int N, int K, int M){ vector<int> v; for (int i = 0; i < N; i++) v.push_back(a[i]); // Right rotate K times while (K--) { rightrotate(v, 1); } // return Mth element return v[M - 1];}// Driver codeint main(){ // Array initialization int a[] = { 1, 2, 3, 4, 5 }; int N = sizeof(a) / sizeof(a[0]); int K = 3, M = 2; // Function call cout << getFirstElement(a, N, K, M); return 0;} |
Java
import java.util.Arrays;public class GFG { // In-place rotates array towards left by d static void leftRotate(int[] arr, int d) { int n = arr.length; reverse(arr, 0, d - 1); reverse(arr, d, n - 1); reverse(arr, 0, n - 1); } // In-place rotates array towards right by d static void rightRotate(int[] arr, int d) { int n = arr.length; leftRotate(arr, n - d); } // Helper function to reverse a subarray static void reverse(int[] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // Function to return Mth element of array after K right rotations static int getFirstElement(int[] arr, int K, int M) { int[] rotatedArray = Arrays.copyOf(arr, arr.length); // Right rotate K times for (int i = 0; i < K; i++) { rightRotate(rotatedArray, 1); } // Return Mth element return rotatedArray[M - 1]; } public static void main(String[] args) { // Array initialization int[] arr = {1, 2, 3, 4, 5}; int K = 3; int M = 2; // Function call System.out.println(getFirstElement(arr, K, M)); }} |
Python3
def left_rotate(v, d): v[:d] = v[:d][::-1] v[d:] = v[d:][::-1] v[:] = v[::-1]def right_rotate(v, d): left_rotate(v, len(v) - d)def get_first_element(a, K, M): v = list(a) # Right rotate K times while K > 0: right_rotate(v, 1) K -= 1 # Return Mth element return v[M - 1]# Driver codea = [1, 2, 3, 4, 5]K = 3M = 2# Function callprint(get_first_element(a, K, M))# This code is contributed by Dwaipayan Bandyopadhyay |
C#
// C# program to find the Mth element// of the array after K right rotations.using System;using System.Linq;class GFG{ // In-place rotates array towards left by d static void leftrotate(ref int[] v, int d) { Array.Reverse(v, 0, d); Array.Reverse(v, d, v.Length - d); Array.Reverse(v); } // In-place rotates array towards right by d static void reftrotate(ref int[] v, int d) { leftrotate(ref v, v.Length - d); } // Function to return Mth element of // array after K right rotations static int getFirstElement(int[] a, int K, int M) { int[] v = a.ToArray(); // Right rotate K times while (K > 0) { reftrotate(ref v, 1); K--; } // return Mth element return v[M - 1]; } static void Main(string[] args) { // Array initialization int[] a = { 1, 2, 3, 4, 5 }; int N = a.Length; int K = 3, M = 2; // Function call Console.WriteLine(getFirstElement(a, K, M)); }} |
Javascript
// Javascript program to find the Mth element// of the array after K right rotations// In-place rotates s towards left by dfunction leftrotate(v, d) { const reversedFirstPart = v.slice(0, d).reverse(); const reversedSecondPart = v.slice(d).reverse(); const reversedArray = reversedFirstPart.concat(reversedSecondPart).reverse(); for (let i = 0; i < v.length; i++) { v[i] = reversedArray[i]; }}// In-place rotates s towards right by dfunction rightrotate(v, d) { leftrotate(v, v.length - d);}// Function to return Mth element of// array after k right rotationsfunction getFirstElement(a, N, K, M) { let v = []; for (let i = 0; i < N; i++) { v.push(a[i]); } // Right rotate K times while (K--) { rightrotate(v, 1); } // return Mth element return v[M - 1];}// Driver code// Array initializationlet a = [1, 2, 3, 4, 5];let N = a.length;let K = 3;let 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<bits/stdc++.h>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;}// Driver Code int main() { int a[] = { 1, 2, 3, 4, 5 }; int N = sizeof(a) / sizeof(a[0]); int K = 3, M = 2; cout << getFirstElement(a, N, K, M); return 0; } |
Java
// Java program to implement// the above approachclass GFG{ // Function to return Mth element of// array after k right rotationsstatic 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 Ritik Bansal |
Python3
# Python3 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 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) result = a[index] # Return the result return result# Driver Codeif __name__ == "__main__": a = [ 1, 2, 3, 4, 5 ] N = len(a) K , M = 3, 2 print( getFirstElement(a, N, K, M))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to return Mth element of// array after k right rotationsstatic 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() { int []a = { 1, 2, 3, 4, 5 }; int N = 5; int K = 3, M = 2; Console.Write(getFirstElement(a, N, K, M)); }} // This code is contributed by Code_Mech |
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> |
Output
4
Time Complexity: O(1)
Auxiliary Space: O(1)
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!
