Given two sorted arrays A[] and B[] consisting of N distinct integers, the task is to rearrange the elements of array B[] such that, for every ith index, A[i] is not equal to B[i]. If multiple such arrangements exist, print any one of them. If no such arrangement exists, print -1.
Examples:
Input: A[] = {2, 4, 5, 8}, B[] = {2, 4, 5, 8}
Output: 4 2 8 5
Explanation:
Possible arrangements that satisfy the required conditions are {4, 2, 8, 5}, {8, 5, 4, 2} and {8, 5, 4, 2}.Input: A[] = {1, 3, 4, 5}, B[] = {2, 4, 6, 7}
Output: 7 6 2 4
Naive approach: The simplest approach is to find all possible permutations of array B[] and print any permutation among them such that, for every ith index, A[i]) is not equal to B[i].
Time Complexity: O(N*N!)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use a Greedy Approach to find the required arrangement of array B[] by using the condition that both the arrays consist of N distinct elements in ascending order. Follow the steps below to solve the problem:
- Reverse the given array B[].
- If N is 1 and A[0] = B[0], then print -1.
- Otherwise, iterate over the arrays, and check if A[i] equals to B[i] or not.
- If A[i] equals to B[i], swap B[i] with B[i+1] and break the loop.
- After the above steps, print the array B[].
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std; // Function to find the arrangement// of array B[] such that element at// each index of A[] and B[] are not equalvoid RearrangeB(int A[], vector<int> B, int n){ // Print not possible, if arrays // only have single equal element if (n == 1 && A[0] == B[0]) { cout << "-1" << endl; return; } // Reverse array B for(int i = 0; i < n / 2; i++) { int t = B[i]; B[i] = B[n - i - 1]; B[n - i - 1] = t; } // Traverse over arrays to check // if there is any index where // A[i] and B[i] are equal for(int i = 0; i < n - 1; i++) { // Swap B[i] with B[i - 1] if (B[i] == A[i]) { int t = B[i + 1]; B[i + 1] = B[i]; B[i] = t; // Break the loop break; } } // Print required arrangement // of array B for(int k : B) cout << k << " ";} // Driver Codeint main(){ // Given arrays A[] and B[] int A[] = { 2, 4, 5, 8 }; vector<int> B = { 2, 4, 5, 8 }; // Length of array A[] int n = sizeof(A) / sizeof(A[0]); // Function call RearrangeB(A, B, n);}// This code is contributed by sanjoy_62 |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG { // Function to find the arrangement // of array B[] such that element at // each index of A[] and B[] are not equal static void RearrangeB(int[] A, int[] B) { // Length of array int n = A.length; // Print not possible, if arrays // only have single equal element if (n == 1 && A[0] == B[0]) { System.out.println("-1"); return; } // Reverse array B for (int i = 0; i < n / 2; i++) { int t = B[i]; B[i] = B[n - i - 1]; B[n - i - 1] = t; } // Traverse over arrays to check // if there is any index where // A[i] and B[i] are equal for (int i = 0; i < n - 1; i++) { // Swap B[i] with B[i - 1] if (B[i] == A[i]) { int t = B[i + 1]; B[i + 1] = B[i]; B[i] = t; // Break the loop break; } } // Print required arrangement // of array B for (int k : B) System.out.print(k + " "); } // Driver Code public static void main(String[] args) { // Given arrays A[] and B[] int[] A = { 2, 4, 5, 8 }; int[] B = { 2, 4, 5, 8 }; // Function Call RearrangeB(A, B); }} |
Python3
# Python3 program for the above approach # Function to find the arrangement # of array B[] such that element at# each index of A[] and B[] are not equaldef RearrangeB(A, B): # Length of array n = len(A) # Print not possible, if arrays # only have single equal element if (n == 1 and A[0] == B[0]): print(-1) return # Reverse array B for i in range(n // 2): t = B[i] B[i] = B[n - i - 1] B[n - i - 1] = t # Traverse over arrays to check # if there is any index where # A[i] and B[i] are equal for i in range(n - 1): # Swap B[i] with B[i - 1] if (B[i] == A[i]): B[i], B[i - 1] = B[i - 1], B[i] break # Print required arrangement # of array B for k in B: print(k, end = " ")# Driver Code# Given arrays A[] and B[]A = [ 2, 4, 5, 8 ]B = [ 2, 4, 5, 8 ]# Function callRearrangeB(A, B)# This code is contributed by Shivam Singh |
C#
// C# program for // the above approachusing System;class GFG{// Function to find the arrangement// of array []B such that element at// each index of []A and []B // are not equalstatic void RearrangeB(int[] A, int[] B){ // Length of array int n = A.Length; // Print not possible, if arrays // only have single equal element if (n == 1 && A[0] == B[0]) { Console.WriteLine("-1"); return; } // Reverse array B for (int i = 0; i < n / 2; i++) { int t = B[i]; B[i] = B[n - i - 1]; B[n - i - 1] = t; } // Traverse over arrays to check // if there is any index where // A[i] and B[i] are equal for (int i = 0; i < n - 1; i++) { // Swap B[i] with B[i - 1] if (B[i] == A[i]) { int t = B[i + 1]; B[i + 1] = B[i]; B[i] = t; // Break the loop break; } } // Print required arrangement // of array B foreach (int k in B) Console.Write(k + " ");}// Driver Codepublic static void Main(String[] args){ // Given arrays []A and []B int[] A = {2, 4, 5, 8}; int[] B = {2, 4, 5, 8}; // Function Call RearrangeB(A, B);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the// above approach // Function to find the arrangement // of array B[] such that element at // each index of A[] and B[] are not equal function RearrangeB( A, B) { // Length of array let n = A.length; // Print not possible, if arrays // only have single equal element if (n == 1 && A[0] == B[0]) { document.write("-1"); return; } // Reverse array B for (let i = 0; i < n / 2; i++) { let t = B[i]; B[i] = B[n - i - 1]; B[n - i - 1] = t; } // Traverse over arrays to check // if there is any index where // A[i] and B[i] are equal for (let i = 0; i < n - 1; i++) { // Swap B[i] with B[i - 1] if (B[i] == A[i]) { let t = B[i + 1]; B[i + 1] = B[i]; B[i] = t; // Break the loop break; } } // Print required arrangement // of array B for (let k in B) document.write(B[k] + " "); } // Driver Code // Given arrays A[] and B[] let A = [ 2, 4, 5, 8 ]; let B = [ 2, 4, 5, 8 ]; // Function Call RearrangeB(A, B); // This code is contributed by avijitmondal1998.</script> |
Output:
8 5 4 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!
