Given two arrays A[] and B[] of equal size N, the task is to check whether A[] can be made equal to B[] by reversing any sub-array of A only once.
Examples:
Input: A[] = {1, 3, 2, 4}
B[] = {1, 2, 3, 4}
Output: Yes
Explanation:
The sub-array {3, 2} can be reversed to {2, 3}, which makes A equal to B.
Input: A[] = {1, 4, 2, 3}
B[] = {1, 2, 3, 4}
Output: No
Explanation:
There is no sub-array of A which, when reversed, makes A equal to B.
Naive Approach: Check for all sub-arrays of A[] and compare the two arrays after reversing the sub-array.
Time complexity: O(N2).
Efficient Approach:
- First, find the starting and the ending index of the sub-array not equal in A and B.
- Then, by reversing the required sub-array, we can check whether A can be made equal to B or not.
- The starting index is the first index in the arrays for which A[i] != B[i] and the ending index is the last index in arrays for which A[i] != B[i].
Below is the implementation of the above approach.
C++
// C++ implementation to// check whether two arrays// can be made equal by// reversing a sub-array// only once#include <bits/stdc++.h>using namespace std;// Function to check whether two arrays// can be made equal by reversing// a sub-array only oncevoid checkArray(int A[], int B[], int N){ // Integer variable for // storing the required // starting and ending // indices in the array int start = 0; int end = N - 1; // Finding the smallest index // for which A[i] != B[i] // i.e the starting index // of the unequal sub-array for (int i = 0; i < N; i++) { if (A[i] != B[i]) { start = i; break; } } // Finding the largest index // for which A[i] != B[i] // i.e the ending index // of the unequal sub-array for (int i = N - 1; i >= 0; i--) { if (A[i] != B[i]) { end = i; break; } } // Reversing the sub-array // A[start], A[start+1] .. A[end] reverse(A + start, A + end + 1); // Checking whether on reversing // the sub-array A[start]...A[end] // makes the arrays equal for (int i = 0; i < N; i++) { if (A[i] != B[i]) { // If any element of the // two arrays is unequal // print No and return cout << "No" << endl; return; } } // Print Yes if arrays are // equal after reversing // the sub-array cout << "Yes" << endl;}// Driver codeint main(){ int A[] = { 1, 3, 2, 4 }; int B[] = { 1, 2, 3, 4 }; int N = sizeof(A) / sizeof(A[0]); checkArray(A, B, N); return 0;} |
Java
// Java implementation to// check whether two arrays// can be made equal by// reversing a sub-array// only onceimport java.util.*; class GFG{ // Function to check whether two arrays// can be made equal by reversing// a sub-array only oncestatic void checkArray(int A[], int B[], int N){ // Integer variable for // storing the required // starting and ending // indices in the array int start = 0; int end = N - 1; // Finding the smallest index // for which A[i] != B[i] // i.e the starting index // of the unequal sub-array for (int i = 0; i < N; i++) { if (A[i] != B[i]) { start = i; break; } } // Finding the largest index // for which A[i] != B[i] // i.e the ending index // of the unequal sub-array for (int i = N - 1; i >= 0; i--) { if (A[i] != B[i]) { end = i; break; } } // Reversing the sub-array // A[start], A[start+1] .. A[end] Collections.reverse(Arrays.asList(A)); // Checking whether on reversing // the sub-array A[start]...A[end] // makes the arrays equal for (int i = 0; i < N; i++) { if (A[i] != B[i]) { // If any element of the // two arrays is unequal // print No and return System.out.println("No"); return; } } // Print Yes if arrays are // equal after reversing // the sub-array System.out.println("Yes");}// Driver codepublic static void main(String[] args) { int A[] = { 1, 3, 2, 4 }; int B[] = { 1, 2, 3, 4 }; int N = A.length; checkArray(A, B, N);}}// This Code is contributed by rock_cool |
Python3
# Python3 implementation to# check whether two arrays# can be made equal by# reversing a sub-array# only once# Function to check whether two arrays# can be made equal by reversing# a sub-array only oncedef checkArray(A, B, N): # Integer variable for # storing the required # starting and ending # indices in the array start = 0 end = N - 1 # Finding the smallest index # for which A[i] != B[i] # i.e the starting index # of the unequal sub-array for i in range(N): if (A[i] != B[i]): start = i break # Finding the largest index # for which A[i] != B[i] # i.e the ending index # of the unequal sub-array for i in range(N - 1, -1, -1): if (A[i] != B[i]): end = i break # Reversing the sub-array # A[start], A[start+1] .. A[end] A[start:end + 1] = reversed(A[start:end + 1]) # Checking whether on reversing # the sub-array A[start]...A[end] # makes the arrays equal for i in range(N): if (A[i] != B[i]): # If any element of the # two arrays is unequal # print No and return print("No") return # Print Yes if arrays are # equal after reversing # the sub-array print("Yes") # Driver codeif __name__ == '__main__': A = [ 1, 3, 2, 4 ] B = [ 1, 2, 3, 4 ] N = len(A) checkArray(A, B, N) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to// check whether two arrays// can be made equal by// reversing a sub-array// only onceusing System;class GFG{// Function to check whether two arrays// can be made equal by reversing// a sub-array only oncestatic void checkArray(int []A, int []B, int N){ // Integer variable for // storing the required // starting and ending // indices in the array int start = 0; int end = N - 1; // Finding the smallest index // for which A[i] != B[i] // i.e the starting index // of the unequal sub-array for(int i = 0; i < N; i++) { if (A[i] != B[i]) { start = i; break; } } // Finding the largest index // for which A[i] != B[i] // i.e the ending index // of the unequal sub-array for(int i = N - 1; i >= 0; i--) { if (A[i] != B[i]) { end = i; break; } } // Reversing the sub-array // A[start], A[start+1] .. A[end] Array.Reverse(A, start, end); // Checking whether on reversing // the sub-array A[start]...A[end] // makes the arrays equal for(int i = 0; i < N; i++) { if (A[i] != B[i]) { // If any element of the // two arrays is unequal // print No and return Console.Write("No"); return; } } // Print Yes if arrays are // equal after reversing // the sub-array Console.Write("Yes");}// Driver codepublic static void Main(string[] args) { int []A = { 1, 3, 2, 4 }; int []B = { 1, 2, 3, 4 }; int N = A.Length; checkArray(A, B, N);}}// This code is contributed by rutvik_56 |
Javascript
<script>// Javascript implementation to// check whether two arrays// can be made equal by// reversing a sub-array// only once// Function to check whether two arrays// can be made equal by reversing// a sub-array only oncefunction checkArray(A, B, N){ // Integer variable for // storing the required // starting and ending // indices in the array var start = 0; var end = N - 1; // Finding the smallest index // for which A[i] != B[i] // i.e the starting index // of the unequal sub-array for (var i = 0; i < N; i++) { if (A[i] != B[i]) { start = i; break; } } // Finding the largest index // for which A[i] != B[i] // i.e the ending index // of the unequal sub-array for (var i = N - 1; i >= 0; i--) { if (A[i] != B[i]) { end = i; break; } } // Reversing the sub-array // A[start], A[start+1] .. A[end] var l = start; var r = end; var d = parseInt((r-l+2)/2); for(var i=0;i<d;i++) { var t = A[l+i]; A[l+i] = A[r-i]; A[r-i] = t; } // Checking whether on reversing // the sub-array A[start]...A[end] // makes the arrays equal for (var i = 0; i < N; i++) { if (A[i] != B[i]) { // If any element of the // two arrays is unequal // print No and return document.write( "No" ); return; } } // Print Yes if arrays are // equal after reversing // the sub-array document.write( "Yes" );}// Driver codevar A = [1, 3, 2, 4];var B = [1, 2, 3, 4];var N = A.length;checkArray(A, B, N);</script> |
Output:
Yes
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!
