Given arrays, A[] and array B[] of size N, the task is to minimize the number of rotations (left or right) on A such that it becomes equal to B.
Note: It is always possible to change A to B.
Examples:
Input: A[] = {1, 2, 3, 4, 5},
B[] = {4, 5, 1, 2, 3}
Output: 2
Explanation: A[] can be changed to B[]:
On left rotating A[] 3 or,
On right rotating A[] 2 times.
Hence, the minimum number of rotations required are 2.Input: A[] = {13, 12, 7, 18, 4, 5, 1},
B[] = {12, 7, 18, 4, 5, 1, 13}
Output: 1
Explanation: A[] can be changed to B[]:
On left rotating A[] 1 time or,
On right rotating A[] 6 times.
Hence, the minimum number of rotations required is 1.
Approach: The solution is based on simply keeping rotating the array A[] and checking it. Follow the steps mentioned below:
- Left rotate array A[] until it is equal to B[] and count the number of rotations required.
- Similarly right rotate array A[] until it is equal to B[] and count the number of rotations.
- The minimum of both the rotations will be the answer.
Below is the implementation of the above method:
C++
// C++ code to minimize number of rotations#include <bits/stdc++.h>using namespace std;// Function to check if two arrays are equalbool check(int A[], int B[], int N){ bool flag = true; for (int i = 0; i < N; i++) { if (A[i] != B[i]) { flag = false; break; } } return flag;}// Function to left rotate an arrayvoid Leftrotate(int A[], int N){ int temp = A[0]; for (int i = 0; i < N - 1; i++) { A[i] = A[i + 1]; } A[N - 1] = temp;}// Function to right rotate an arrayvoid Rightrotate(int A[], int N){ int temp = A[N - 1]; for (int i = N - 1; i > 0; i--) { A[i] = A[i - 1]; } A[0] = temp;}// Function to minimize number of rotationsint minRotations(int A[], int B[], int N){ int C[N]; for (int i = 0; i < N; i++) C[i] = A[i]; int a = 0, b = 0; // Right rotate the array // till it is equal to B while (check(A, B, N) == false) { Rightrotate(A, N); a++; } // Left rotate the array // till it is equal to B while (check(C, B, N) == false) { Leftrotate(C, N); b++; } int ans = min(a, b); return ans;}// Driver codeint main(){ int A[] = { 13, 12, 7, 18, 4, 5, 1 }; int B[] = { 12, 7, 18, 4, 5, 1, 13 }; int N = sizeof(A) / sizeof(A[0]); int ans = minRotations(A, B, N); cout << ans; return 0;} |
C
// C code to minimize number of rotations#include <stdbool.h>#include <stdio.h>#include <stdlib.h>// Function to check if two arrays are equalbool check(int A[], int B[], int N){ bool flag = true; for (int i = 0; i < N; i++) { if (A[i] != B[i]) { flag = false; break; } } return flag;}// Function to left rotate an arrayvoid Leftrotate(int A[], int N){ int temp = A[0]; for (int i = 0; i < N - 1; i++) { A[i] = A[i + 1]; } A[N - 1] = temp;}// Function to right rotate an arrayvoid Rightrotate(int A[], int N){ int temp = A[N - 1]; for (int i = N - 1; i > 0; i--) { A[i] = A[i - 1]; } A[0] = temp;}// Function to minimize number of rotationsint minRotations(int A[], int B[], int N){ int ans, a = 0, b = 0; int C[N]; for (int i = 0; i < N; i++) C[i] = A[i]; // Right rotate the array // till it is equal to B while (check(A, B, N) == false) { Rightrotate(A, N); a++; } // Left rotate the array // till it is equal to B while (check(C, B, N) == false) { Leftrotate(C, N); b++; } ans = a <= b ? a : b; return ans;}// Driver codeint main(){ int A[] = { 13, 12, 7, 18, 4, 5, 1 }; int B[] = { 12, 7, 18, 4, 5, 1, 13 }; int N = sizeof(A) / sizeof(A[0]); int ans = minRotations(A, B, N); printf("%d", ans); return 0;} |
Java
// Java code to minimize number of rotationsimport java.util.*;public class GFG{ // Function to check if two arrays are equalstatic boolean check(int A[], int B[], int N){ boolean flag = true; for (int i = 0; i < N; i++) { if (A[i] != B[i]) { flag = false; break; } } return flag;}// Function to left rotate an arraystatic void Leftrotate(int A[], int N){ int temp = A[0]; for (int i = 0; i < N - 1; i++) { A[i] = A[i + 1]; } A[N - 1] = temp;}// Function to right rotate an arraystatic void Rightrotate(int A[], int N){ int temp = A[N - 1]; for (int i = N - 1; i > 0; i--) { A[i] = A[i - 1]; } A[0] = temp;}// Function to minimize number of rotationsstatic int minRotations(int A[], int B[], int N){ int C[] = new int[N]; for (int i = 0; i < N; i++) C[i] = A[i]; int a = 0, b = 0; // Right rotate the array // till it is equal to B while (check(A, B, N) == false) { Rightrotate(A, N); a++; } // Left rotate the array // till it is equal to B while (check(C, B, N) == false) { Leftrotate(C, N); b++; } int ans = Math.min(a, b); return ans;}// Driver codepublic static void main(String args[]){ int A[] = { 13, 12, 7, 18, 4, 5, 1 }; int B[] = { 12, 7, 18, 4, 5, 1, 13 }; int N = A.length; int ans = minRotations(A, B, N); System.out.println(ans);}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach # Function to check if two arrays are equaldef check(A, B, N): flag = True; for i in range(N): if (A[i] != B[i]): flag = False; break; return flag;# Function to left rotate an arraydef Leftrotate(A, N): temp = A[0]; for i in range(N - 1): A[i] = A[i + 1]; A[N - 1] = temp;# Function to right rotate an arraydef Rightrotate(A, N): temp = A[N - 1]; for i in range(N - 1, 0, -1): A[i] = A[i - 1]; A[0] = temp;# Function to minimize number of rotationsdef minRotations(A, B, N): C = [0] * N for i in range(N): C[i] = A[i]; a = 0 b = 0 # Right rotate the array # till it is equal to B while (check(A, B, N) == False): Rightrotate(A, N); a += 1 # Left rotate the array # till it is equal to B while (check(C, B, N) == False): Leftrotate(C, N); b += 1 ans = min(a, b); return ans;# Driver codeA = [13, 12, 7, 18, 4, 5, 1];B = [12, 7, 18, 4, 5, 1, 13];N = len(A)ans = minRotations(A, B, N);print(ans);# This code is contributed by gfgking |
C#
// C# code to minimize number of rotationsusing System;public class GFG{ // Function to check if two arrays are equal static bool check(int[] A, int[] B, int N) { bool flag = true; for (int i = 0; i < N; i++) { if (A[i] != B[i]) { flag = false; break; } } return flag; } // Function to left rotate an array static void Leftrotate(int[] A, int N) { int temp = A[0]; for (int i = 0; i < N - 1; i++) { A[i] = A[i + 1]; } A[N - 1] = temp; } // Function to right rotate an array static void Rightrotate(int[] A, int N) { int temp = A[N - 1]; for (int i = N - 1; i > 0; i--) { A[i] = A[i - 1]; } A[0] = temp; } // Function to minimize number of rotations static int minRotations(int[] A, int[] B, int N) { int[] C = new int[N]; for (int i = 0; i < N; i++) C[i] = A[i]; int a = 0, b = 0; // Right rotate the array // till it is equal to B while (check(A, B, N) == false) { Rightrotate(A, N); a++; } // Left rotate the array // till it is equal to B while (check(C, B, N) == false) { Leftrotate(C, N); b++; } int ans = Math.Min(a, b); return ans; } // Driver code public static void Main() { int[] A = { 13, 12, 7, 18, 4, 5, 1 }; int[] B = { 12, 7, 18, 4, 5, 1, 13 }; int N = A.Length; int ans = minRotations(A, B, N); Console.Write(ans); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript code for the above approach // Function to check if two arrays are equal function check(A, B, N) { let flag = true; for (let i = 0; i < N; i++) { if (A[i] != B[i]) { flag = false; break; } } return flag; } // Function to left rotate an array function Leftrotate(A, N) { let temp = A[0]; for (let i = 0; i < N - 1; i++) { A[i] = A[i + 1]; } A[N - 1] = temp; } // Function to right rotate an array function Rightrotate(A, N) { let temp = A[N - 1]; for (let i = N - 1; i > 0; i--) { A[i] = A[i - 1]; } A[0] = temp; } // Function to minimize number of rotations function minRotations(A, B, N) { let C = new Array(N); for (let i = 0; i < N; i++) C[i] = A[i]; let a = 0, b = 0; // Right rotate the array // till it is equal to B while (check(A, B, N) == false) { Rightrotate(A, N); a++; } // Left rotate the array // till it is equal to B while (check(C, B, N) == false) { Leftrotate(C, N); b++; } let ans = Math.min(a, b); return ans; } // Driver code let A = [13, 12, 7, 18, 4, 5, 1]; let B = [12, 7, 18, 4, 5, 1, 13]; let N = A.length; let ans = minRotations(A, B, N); document.write(ans);// This code is contributed by Potta Lokesh </script> |
Output
1
Time Complexity: O(N2)
Auxiliary Space: O(N), since N extra space has been added.
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!
