Minimize number of rotations on array A such that it becomes equal to B
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 equal 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 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 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 int 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 code int 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 equal 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 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 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 int 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 code int 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 rotations import java.util.*; public class GFG { // Function to check if two arrays are equal static 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 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(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 equal def 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 array def 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 array def 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 rotations def 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 code A = [ 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 rotations using 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> |
1
Time Complexity: O(N2)
Auxiliary Space: O(N), since N extra space has been added.