Check if two arrays can be made equal by swapping pairs of one of the arrays
Given two binary arrays arr1[] and arr2[] of the same size, the task is to make both the arrays equal by swapping pairs of arr1[ ] only if arr1[i] = 0 and arr1[j] = 1 (0 ? i < j < N)). If it is possible to make both the arrays equal, print “Yes”. Otherwise, print “No”.
Examples:
Input: arr1[] = {0, 0, 1, 1}, arr2[] = {1, 1, 0, 0}
Output: Yes
Explanation:
Swap arr1[1] and arr1[3], it becomes arr1[] = {0, 1, 1, 0}.
Swap arr1[0] and arr1[2], it becomes arr1[] = {1, 1, 0, 0}.Input: arr1[] = {1, 0, 1, 0, 1}, arr2[] = {0, 1, 0, 0, 1}
Output: No
Approach: Follow the steps below to solve the problem:
- Initialize two variable, say count and flag (= true).
- Traverse the array and for every array element, perform the following operations:
- If arr1[i] != arr2[i]:
- If arr1[i] == 0, increment count by 1.
- Otherwise, decrement count by 1 and if count < 0, update flag = false.
- If arr1[i] != arr2[i]:
- If flag is equal to true, print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to check if two arrays // can be made equal or not by swapping // pairs of only one of the arrays void checkArrays( int arr1[], int arr2[], int N) { // Stores elements required // to be replaced int count = 0; // To check if the arrays // can be made equal or not bool flag = true ; // Traverse the array for ( int i = 0; i < N; i++) { // If array elements are not equal if (arr1[i] != arr2[i]) { if (arr1[i] == 0) // Increment count by 1 count++; else { // Decrement count by 1 count--; if (count < 0) { flag = 0; break ; } } } } // If flag is true and count is 0, // print "Yes". Otherwise "No" if (flag && count == 0) cout << "Yes" << endl; else cout << "No" << endl; } // Driver Code int main() { // Given arrays int arr1[] = { 0, 0, 1, 1 }; int arr2[] = { 1, 1, 0, 0 }; // Size of the array int N = sizeof (arr1) / sizeof (arr1[0]); checkArrays(arr1, arr2, N); return 0; } |
Java
// Java program for above approach public class GFG { // Function to check if two arrays // can be made equal or not by swapping // pairs of only one of the arrays static void checkArrays( int arr1[], int arr2[], int N) { // Stores elements required // to be replaced int count = 0 ; // To check if the arrays // can be made equal or not boolean flag = true ; // Traverse the array for ( int i = 0 ; i < N; i++) { // If array elements are not equal if (arr1[i] != arr2[i]) { if (arr1[i] == 0 ) // Increment count by 1 count++; else { // Decrement count by 1 count--; if (count < 0 ) { flag = false ; break ; } } } } // If flag is true and count is 0, // print "Yes". Otherwise "No" if ((flag && (count == 0 )) == true ) System.out.println( "Yes" ); else System.out.println( "No" ); } // Driver Code public static void main (String[] args) { // Given arrays int arr1[] = { 0 , 0 , 1 , 1 }; int arr2[] = { 1 , 1 , 0 , 0 }; // Size of the array int N = arr1.length; checkArrays(arr1, arr2, N); } } // This code is contributed by AnkThon |
Python3
# Python3 program for above approach # Function to check if two arrays # can be made equal or not by swapping # pairs of only one of the arrays def checkArrays(arr1, arr2, N): # Stores elements required # to be replaced count = 0 # To check if the arrays # can be made equal or not flag = True # Traverse the array for i in range (N): # If array elements are not equal if (arr1[i] ! = arr2[i]): if (arr1[i] = = 0 ): # Increment count by 1 count + = 1 else : # Decrement count by 1 count - = 1 if (count < 0 ): flag = 0 break # If flag is true and count is 0, # pr"Yes". Otherwise "No" if (flag and count = = 0 ): print ( "Yes" ) else : print ( "No" ) # Driver Code if __name__ = = '__main__' : # Given arrays arr1 = [ 0 , 0 , 1 , 1 ] arr2 = [ 1 , 1 , 0 , 0 ] # Size of the array N = len (arr1) checkArrays(arr1, arr2, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG{ // Function to check if two arrays // can be made equal or not by swapping // pairs of only one of the arrays static void checkArrays( int [] arr1, int [] arr2, int N) { // Stores elements required // to be replaced int count = 0; // To check if the arrays // can be made equal or not bool flag = true ; // Traverse the array for ( int i = 0; i < N; i++) { // If array elements are not equal if (arr1[i] != arr2[i]) { if (arr1[i] == 0) // Increment count by 1 count++; else { // Decrement count by 1 count--; if (count < 0) { flag = false ; break ; } } } } // If flag is true and count is 0, // print "Yes". Otherwise "No" if ((flag && (count == 0)) == true ) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } // Driver Code static public void Main() { // Given arrays int [] arr1 = { 0, 0, 1, 1 }; int [] arr2 = { 1, 1, 0, 0 }; // Size of the array int N = arr1.Length; checkArrays(arr1, arr2, N); } } // This code is contributed by susmitakundugoaldanga. |
Javascript
<script> // Java script program for above approach // Function to check if two arrays // can be made equal or not by swapping // pairs of only one of the arrays function checkArrays(arr1,arr2,N) { // Stores elements required // to be replaced let count = 0; // To check if the arrays // can be made equal or not let flag = true ; // Traverse the array for (let i = 0; i < N; i++) { // If array elements are not equal if (arr1[i] != arr2[i]) { if (arr1[i] == 0) // Increment count by 1 count++; else { // Decrement count by 1 count--; if (count < 0) { flag = false ; break ; } } } } // If flag is true and count is 0, // print "Yes". Otherwise "No" if ((flag && (count == 0)) == true ) document.write( "Yes" ); else document.write( "No" ); } // Driver Code // Given arrays let arr1 = [ 0, 0, 1, 1 ]; let arr2 = [ 1, 1, 0, 0 ]; // Size of the array let N = arr1.length; checkArrays(arr1, arr2, N); // This code is contributed by Gottumukkala Sravan Kumar (171fa07058) </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Define two binary arrays arr1[] and arr2[] of the same size.
- Calculate the size of the arrays using the sizeof() operator and store it in the variable n.
- Initialize three integer variables zero_count, one_count, and mismatch_count to zero.
- Use a for loop to iterate through the arrays from 0 to n-1.
- Inside the for loop, check if the current element of arr1 is zero. If yes, increment the zero_count variable. Otherwise, increment the one_count variable.
- Also inside the for loop, check if the current element of arr1 is not equal to the current element of arr2. If yes, increment the mismatch_count variable.
- After the for loop, check if the zero_count and one_count variables are equal and the mismatch_count variable is even. If yes, print “Yes”. Otherwise, print “No”.
- End the program.
Below is the implementation of the above approach:
C++
#include <iostream> using namespace std; int main() { int arr1[] = {0, 0, 1, 1}; int arr2[] = {1, 1, 0, 0}; int n = sizeof (arr1) / sizeof (arr1[0]); // calculate size of arrays int zero_count = 0, one_count = 0, mismatch_count = 0; for ( int i = 0; i < n; i++) { if (arr1[i] == 0) { zero_count++; // count the number of zeros in arr1 } else { one_count++; // count the number of ones in arr1 } if (arr1[i] != arr2[i]) { mismatch_count++; // count the number of mismatches between arr1 and arr2 } } if (zero_count == one_count && mismatch_count % 2 == 0) { cout << "Yes" ; // if the number of zeros and ones in arr1 are equal and the number of mismatches is even, we can make both arrays equal by swapping pairs of arr1 } else { cout << "No" ; // otherwise, we cannot make both arrays equal by swapping pairs of arr1 } return 0; } // This code is contributed by rudra1807raj |
Java
public class Main { public static void main(String[] args) { int [] arr1 = { 0 , 0 , 1 , 1 }; int [] arr2 = { 1 , 1 , 0 , 0 }; int n = arr1.length; // Calculate the size of arrays int zeroCount = 0 , oneCount = 0 , mismatchCount = 0 ; for ( int i = 0 ; i < n; i++) { if (arr1[i] == 0 ) { zeroCount++; // Count the number of zeros in arr1 } else { oneCount++; // Count the number of ones in arr1 } if (arr1[i] != arr2[i]) { mismatchCount++; // Count the number of mismatches between arr1 and arr2 } } if (zeroCount == oneCount && mismatchCount % 2 == 0 ) { System.out.println( "Yes" ); // If the number of zeros and ones in arr1 are equal and the number of mismatches is even, we can make both arrays equal by swapping pairs of arr1 } else { System.out.println( "No" ); // Otherwise, we cannot make both arrays equal by swapping pairs of arr1 } } } //This code is Contributed by chinmaya121221 |
Python3
# Given arrays arr1 = [ 0 , 0 , 1 , 1 ] arr2 = [ 1 , 1 , 0 , 0 ] n = len (arr1) # calculate size of arrays zero_count = 0 one_count = 0 mismatch_count = 0 # Loop through each element of the arrays for i in range (n): # Count the number of zeros in arr1 if arr1[i] = = 0 : zero_count + = 1 else : one_count + = 1 # Count the number of ones in arr1 # Count the number of mismatches between arr1 and arr2 if arr1[i] ! = arr2[i]: mismatch_count + = 1 # Check the conditions to determine if it's possible to make both arrays equal if zero_count = = one_count and mismatch_count % 2 = = 0 : print ( "Yes" ) # If conditions are met, we can make both arrays equal by swapping pairs of arr1 else : print ( "No" ) # Otherwise, we cannot make both arrays equal by swapping pairs of arr1 |
C#
using System; class Program { static void Main() { int [] arr1 = { 0, 0, 1, 1 }; int [] arr2 = { 1, 1, 0, 0 }; int n = arr1.Length; // Calculate the size of arrays int zeroCount = 0, oneCount = 0, mismatchCount = 0; for ( int i = 0; i < n; i++) { if (arr1[i] == 0) { zeroCount++; // Count the number of zeros in arr1 } else { oneCount++; // Count the number of ones in arr1 } if (arr1[i] != arr2[i]) { mismatchCount++; // Count the number of mismatches between arr1 and arr2 } } if (zeroCount == oneCount && mismatchCount % 2 == 0) { Console.WriteLine( "Yes" ); // If the number of zeros and ones // in arr1 are equal and the number of mismatches is // even, we can make both arrays equal by swapping // pairs of arr1 } else { Console.WriteLine( "No" ); // Otherwise, we cannot make both arrays // equal by swapping pairs of arr1 } } } |
Javascript
// Define the main function function main() { // Define two arrays let arr1 = [0, 0, 1, 1]; let arr2 = [1, 1, 0, 0]; // Calculate the size of the arrays let n = arr1.length; // Initialize counters let zero_count = 0; let one_count = 0; let mismatch_count = 0; // Loop through the arrays for (let i = 0; i < n; i++) { if (arr1[i] == 0) { zero_count++; // Count the number of zeros in arr1 } else { one_count++; // Count the number of ones in arr1 } if (arr1[i] !== arr2[i]) { mismatch_count++; // Count the number of mismatches between arr1 and arr2 } } // Check conditions if (zero_count === one_count && mismatch_count % 2 === 0) { console.log( "Yes" ); // If conditions are met, print "Yes" } else { console.log( "No" ); // Otherwise, print "No" } } // Call the main function main(); |
Output:
Yes
Time Complexity: The time complexity of the given code is O(n), where n is the size of the arrays. This is because the code uses a single loop to iterate through both arrays, and each operation inside the loop takes constant time.
Auxiliary Space: The space complexity of the code is O(1), as it uses only a few variables to store the counts and does not allocate any additional memory based on the input size.
Contact Us