Given two arrays arr1[] and arr2[] of size N, consisting of binary integers, the task is to check if arr1[] can be converted to arr2[] by swapping any pair of array elements (arr1[i], arr1[j]) such that i < j and arr1[i] is 1 and arr1[j] is 0 (any number of times). If it is possible to do so, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr1[] = {0, 1, 1, 0}, arr2[] = {0, 0 1, 1}
Output: Yes
Explanation:
The array arr1[] can be made equal to arr2[] by swapping arr1[1] and arr1[3].Input: arr1[] = {1, 0, 1}, arr2[] = {0, 1, 0}
Output: No
Approach: The idea to solve this problem is based on the following observations:
- The operation doesn’t change the frequency of the number of ones and zeros in array arr1[], so if the number of 0s or 1s are different among arrays, they can never become equal with the above operation.
- If some prefix of arr2[] contains more 1s than the prefix of arr1[] of the same length, then it is not possible to make arr1[] and arr2[] equal, since 1 can be shifted to right only.
- Otherwise, in all other cases, arrays can be made equal.
Follow the below steps to solve the problem:
- Initialize a variable, say count with 0, to store the differences of the prefix sum of arr1[] and arr2[].
- Count the number of 1s and 0s in both arrays and check if the number of 1s and 0s in arr1[] is not equal to the number of 1s and 0s in arr2[] and then print “No”.
- Iterate over the range [1, N – 1] using the variable i and do the following:
- Add the value (arr1[i] – arr2[i]) to the variable count.
- If the value of count is less than 0, then print “No” else continue for the next pair of elements.
- After completing the above steps, if the count isn’t negative at any step then print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if arr1[] can be// converted to arr2[] by swapping pair// (i, j) such that i < j and arr[i] is// 1 and arr[j] is 0void canMakeEqual(int arr1[], int arr2[], int N){ // Stores the differences of prefix // sum of arr1 and arr2 int count = 0; // Stores the count of 1 and // zero of arr1 int arr1_one = 0, arr1_zero = 0; // Stores the count of 1 and // zero of arr2 int arr2_one = 0, arr2_zero = 0; // Iterate in the range [0, N - 1] for (int i = 0; i < N; i++) { // If arr1[i] is 1, then // increment arr1_one by one if (arr1[i] == 1) { arr1_one++; } // Otherwise increment // arr1_zero by one else if (arr1[i] == 0) { arr1_zero++; } // If arr2[i] is 1, then // increment arr2_one by one if (arr2[i] == 1) { arr2_one++; } // Otherwise increment // arr2_zero by one else if (arr2[i] == 0) { arr2_zero++; } } // Check if number of 1s and 0s // of arr1 is equal to number of // 1s and 0s of arr2 respectievly if (arr1_one != arr2_one || arr1_zero != arr2_zero) { cout << "No"; return; } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Increment count by differences // arr1[i] and arr2[i] count = count + (arr1[i] - arr2[i]); // Check if number of 1's in // arr2 are more than arr1 and // then print "No" if (count < 0) { cout << "No"; return; } } // Finally, print "Yes" cout << "Yes";}// Driver Codeint main(){ // Given input arrays int arr1[] = { 0, 1, 1, 0 }; int arr2[] = { 0, 0, 1, 1 }; // Size of the array int N = sizeof(arr1) / sizeof(arr1[0]); // Function Call canMakeEqual(arr1, arr2, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to check if arr1[] can be // converted to arr2[] by swapping pair // (i, j) such that i < j and arr[i] is // 1 and arr[j] is 0 static void canMakeEqual(int []arr1, int []arr2, int N) { // Stores the differences of prefix // sum of arr1 and arr2 int count = 0; // Stores the count of 1 and // zero of arr1 int arr1_one = 0, arr1_zero = 0; // Stores the count of 1 and // zero of arr2 int arr2_one = 0, arr2_zero = 0; // Iterate in the range [0, N - 1] for (int i = 0; i < N; i++) { // If arr1[i] is 1, then // increment arr1_one by one if (arr1[i] == 1) { arr1_one++; } // Otherwise increment // arr1_zero by one else if (arr1[i] == 0) { arr1_zero++; } // If arr2[i] is 1, then // increment arr2_one by one if (arr2[i] == 1) { arr2_one++; } // Otherwise increment // arr2_zero by one else if (arr2[i] == 0) { arr2_zero++; } } // Check if number of 1s and 0s // of arr1 is equal to number of // 1s and 0s of arr2 respectievly if (arr1_one != arr2_one || arr1_zero != arr2_zero) { System.out.print("No"); return; } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Increment count by differences // arr1[i] and arr2[i] count = count + (arr1[i] - arr2[i]); // Check if number of 1's in // arr2 are more than arr1 and // then print "No" if (count < 0) { System.out.print("No"); return; } } // Finally, print "Yes" System.out.print("Yes"); }// Driver Codepublic static void main(String[] args){ // Given input arrays int []arr1 = { 0, 1, 1, 0 }; int []arr2 = { 0, 0, 1, 1 }; // Size of the array int N = arr1.length; // Function Call canMakeEqual(arr1, arr2, N);}}// This code is contributed by code_hunt. |
Python3
# Python 3 program for the above approach# Function to check if arr1[] can be# converted to arr2[] by swapping pair# (i, j) such that i < j and arr[i] is# 1 and arr[j] is 0def canMakeEqual(arr1, arr2, N): # Stores the differences of prefix # sum of arr1 and arr2 count = 0 # Stores the count of 1 and # zero of arr1 arr1_one = 0 arr1_zero = 0 # Stores the count of 1 and # zero of arr2 arr2_one = 0 arr2_zero = 0 # Iterate in the range [0, N - 1] for i in range(N): # If arr1[i] is 1, then # increment arr1_one by one if (arr1[i] == 1): arr1_one += 1 # Otherwise increment # arr1_zero by one elif(arr1[i] == 0): arr1_zero += 1 # If arr2[i] is 1, then # increment arr2_one by one if (arr2[i] == 1): arr2_one += 1 # Otherwise increment # arr2_zero by one elif (arr2[i] == 0): arr2_zero += 1 # Check if number of 1s and 0s # of arr1 is equal to number of # 1s and 0s of arr2 respectievly if (arr1_one != arr2_one or arr1_zero != arr2_zero): print("No") return # Iterate over the range [0, N-1] for i in range(N): # Increment count by differences # arr1[i] and arr2[i] count = count + (arr1[i] - arr2[i]) # Check if number of 1's in # arr2 are more than arr1 and # then print "No" if (count < 0): print("No") return # Finally, print "Yes" print("Yes")# Driver Codeif __name__ == '__main__': # Given input a arr1 = [0, 1, 1, 0] arr2 = [0, 0, 1, 1] # Size of the array N = len(arr1) # Function Call canMakeEqual(arr1, arr2, N) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ // Function to check if arr1[] can be // converted to arr2[] by swapping pair // (i, j) such that i < j and arr[i] is // 1 and arr[j] is 0 static void canMakeEqual(int []arr1, int []arr2, int N) { // Stores the differences of prefix // sum of arr1 and arr2 int count = 0; // Stores the count of 1 and // zero of arr1 int arr1_one = 0, arr1_zero = 0; // Stores the count of 1 and // zero of arr2 int arr2_one = 0, arr2_zero = 0; // Iterate in the range [0, N - 1] for (int i = 0; i < N; i++) { // If arr1[i] is 1, then // increment arr1_one by one if (arr1[i] == 1) { arr1_one++; } // Otherwise increment // arr1_zero by one else if (arr1[i] == 0) { arr1_zero++; } // If arr2[i] is 1, then // increment arr2_one by one if (arr2[i] == 1) { arr2_one++; } // Otherwise increment // arr2_zero by one else if (arr2[i] == 0) { arr2_zero++; } } // Check if number of 1s and 0s // of arr1 is equal to number of // 1s and 0s of arr2 respectievly if (arr1_one != arr2_one || arr1_zero != arr2_zero) { Console.WriteLine("No"); return; } // Iterate over the range [0, N-1] for (int i = 0; i < N; i++) { // Increment count by differences // arr1[i] and arr2[i] count = count + (arr1[i] - arr2[i]); // Check if number of 1's in // arr2 are more than arr1 and // then print "No" if (count < 0) { Console.WriteLine("No"); return; } } // Finally, print "Yes" Console.WriteLine("Yes"); } // Driver Code public static void Main() { // Given input arrays int []arr1 = { 0, 1, 1, 0 }; int []arr2 = { 0, 0, 1, 1 }; // Size of the array int N = arr1.Length; // Function Call canMakeEqual(arr1, arr2, N); }}// This code is contributed by bgangwar59. |
Javascript
<script>// Javascript program for the above approach// Function to check if arr1[] can be// converted to arr2[] by swapping pair// (i, j) such that i < j and arr[i] is// 1 and arr[j] is 0function canMakeEqual(arr1, arr2, N){ // Stores the differences of prefix // sum of arr1 and arr2 var count = 0; // Stores the count of 1 and // zero of arr1 var arr1_one = 0, arr1_zero = 0; // Stores the count of 1 and // zero of arr2 var arr2_one = 0, arr2_zero = 0; // Iterate in the range [0, N - 1] for(var i = 0; i < N; i++) { // If arr1[i] is 1, then // increment arr1_one by one if (arr1[i] == 1) { arr1_one++; } // Otherwise increment // arr1_zero by one else if (arr1[i] == 0) { arr1_zero++; } // If arr2[i] is 1, then // increment arr2_one by one if (arr2[i] == 1) { arr2_one++; } // Otherwise increment // arr2_zero by one else if (arr2[i] == 0) { arr2_zero++; } } // Check if number of 1s and 0s // of arr1 is equal to number of // 1s and 0s of arr2 respectievly if (arr1_one != arr2_one || arr1_zero != arr2_zero) { document.write( "No"); return; } // Iterate over the range [0, N-1] for(var i = 0; i < N; i++) { // Increment count by differences // arr1[i] and arr2[i] count = count + (arr1[i] - arr2[i]); // Check if number of 1's in // arr2 are more than arr1 and // then print "No" if (count < 0) { document.write( "No"); return; } } // Finally, print "Yes" document.write("Yes");}// Driver Code// Given input arraysvar arr1 = [ 0, 1, 1, 0 ];var arr2 = [ 0, 0, 1, 1 ];// Size of the arrayvar N = arr1.length;// Function CallcanMakeEqual(arr1, arr2, N);// This code is contributed by rutvik_56</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!
