Given an array arr[] of size N and a value K (-10^5<K<10^5), the task is to print the array rotated by K times to the right.
Examples:
Input: arr = {1, 3, 5, 7, 9}, K = 2
Output: 7 9 1 3 5
Explanation:
Rotating array 1 time right: 9, 1, 3, 5, 7
Rotating array 2 time right: 7, 9, 1, 3, 5Input: arr = {1, 2, 3, 4, 5}, K = -2
Output: 3 4 5 1 2
Explanation:
Rotating array -1 time right: 2, 3, 4, 5, 1
Rotating array -2 time right: 3, 4, 5, 1, 2
Naive Approach: The brute force approach to solve this problem is to use a temporary array to rotate the array K or -K times.
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: The given problem can be solved by breaking the problem into the following parts:
- Round up the value of K in range [0, N), using below steps:
- If K is negative, first change it into positive, find the modulo with N, and then again change it to negative
- If K is positive, just find the modulo with N
- Handle the case when K is negative. If K is negative, it means we need to rotate the array K times left, or -K times right.
- Next we can simply rotate the array K times by reversing subarrays. Below steps can be followed to solve the problem:
- Reverse all the array elements from 1 to N -1
- Reverse the array elements from 1 to K – 1
- Reverse the array elements from K to N -1
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to rotate the array// to the right, K timesvoid RightRotate(vector<int>& nums, int K){ int n = nums.size(); // Case when K > N or K < -N K = K < 0 ? ((K * -1) % n) * -1 : K % n; // Case when K is negative K = K < 0 ? (n - (K * -1)) : K; // Reverse all the array elements reverse(nums.begin(), nums.end()); // Reverse the first k elements reverse(nums.begin(), nums.begin() + K); // Reverse the elements from K // till the end of the array reverse(nums.begin() + K, nums.end());}// Driver codeint main(){ // Initialize the array vector<int> Array = { 1, 2, 3, 4, 5 }; // Find the size of the array int N = Array.size(); // Initialize K int K = -2; // Call the function and // print the answer RightRotate(Array, K); // Print the array after rotation for (int i = 0; i < N; i++) { cout << Array[i] << " "; } cout << endl; return 0;} |
Java
// Java implementation for the above approachimport java.util.*;class GFG{ // Initialize the array static int[] Array = { 1, 2, 3, 4, 5 }; static void reverse( int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = Array[start]; Array[start] = Array[end]; Array[end] = temp; start++; end--; } } // Function to rotate the array// to the right, K timesstatic void RightRotate( int K){ int n = Array.length; // Case when K > N or K < -N K = K < 0 ? ((K * -1) % n) * -1 : K % n; // Case when K is negative K = K < 0 ? (n - (K * -1)) : K; // Reverse all the array elements reverse(0, n-1); // Reverse the first k elements reverse(0, n - K); // Reverse the elements from K // till the end of the array reverse( K, n-1);}// Driver codepublic static void main(String[] args){ // Find the size of the array int N = Array.length; // Initialize K int K = -2; // Call the function and // print the answer RightRotate(K); // Print the array after rotation for (int i = 0; i < N; i++) { System.out.print(Array[i]+ " "); } System.out.println();}}// This code is contributed by Rajput-Ji |
Python3
# Python code for the above approach # Function to rotate the array# to the right, K timesdef RightRotate(nums, K) : n = len(nums) # Case when K > N or K < -N K = ((K * -1) % n) * -1 if K < 0 else K % n; # Case when K is negative K = (n - (K * -1)) if K < 0 else K; # Reverse all the array elements nums.reverse(); # Reverse the first k elements p1 = nums[0:K] p1.reverse(); # Reverse the elements from K # till the end of the array p2 = nums[K:] p2.reverse(); arr = p1 + p2 return arr;# Driver code# Initialize the arrayArray = [1, 2, 3, 4, 5];# Find the size of the arrayN = len(Array)# Initialize KK = -2;# Call the function and# print the answerArray = RightRotate(Array, K);# Print the array after rotationfor i in Array: print(i, end=" ")# This code is contributed by Saurabh jaiswal |
C#
// C# implementation for the above approachusing System;public class GFG { // Initialize the array static int[] Array = { 1, 2, 3, 4, 5 }; static void reverse(int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = Array[start]; Array[start] = Array[end]; Array[end] = temp; start++; end--; } } // Function to rotate the array // to the right, K times static void RightRotate(int K) { int n = Array.Length; // Case when K > N or K < -N K = K < 0 ? ((K * -1) % n) * -1 : K % n; // Case when K is negative K = K < 0 ? (n - (K * -1)) : K; // Reverse all the array elements reverse(0, n - 1); // Reverse the first k elements reverse(0, n - K); // Reverse the elements from K // till the end of the array reverse(K, n - 1); } // Driver code public static void Main(String[] args) { // Find the size of the array int N = Array.Length; // Initialize K int K = -2; // Call the function and // print the answer RightRotate(K); // Print the array after rotation for (int i = 0; i < N; i++) { Console.Write(Array[i] + " "); } Console.WriteLine(); }}// This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach // Function to rotate the array // to the right, K times function RightRotate(nums, K) { let n = nums.length; // Case when K > N or K < -N K = K < 0 ? ((K * -1) % n) * -1 : K % n; // Case when K is negative K = K < 0 ? (n - (K * -1)) : K; // Reverse all the array elements nums = nums.reverse(); // Reverse the first k elements let p1 = nums.slice(0, K) p1 = p1.reverse(); // Reverse the elements from K // till the end of the array let p2 = nums.slice(K) p2 = p2.reverse(); let arr = p1.concat(p2); return arr; } // Driver code // Initialize the array let Array = [1, 2, 3, 4, 5]; // Find the size of the array let N = Array.length; // Initialize K let K = -2; // Call the function and // print the answer Array = RightRotate(Array, K); // Print the array after rotation for (let i = 0; i < N; i++) { document.write(Array[i] + " "); } document.write('<br>') // This code is contributed by Potta Lokesh </script> |
Output
3 4 5 1 2
Time Complexity: O(N)
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!
