Compruebe si una array se puede convertir en otra array dada intercambiando pares de elementos desiguales

Dadas dos arrays arr1[] y arr2[] de tamaño N , que consisten en enteros binarios, la tarea es comprobar si arr1[] se puede convertir en arr2[] intercambiando cualquier par de elementos de la array (arr1[i], arr1[ j]) tales que i < j y arr1[i] es 1 y arr1[j] es 0 (cualquier número de veces). Si es posible hacerlo, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr1[] = {0, 1, 1, 0}, arr2[] = {0, 0 1, 1}
Salida: Sí
Explicación:
La array arr1[] puede hacerse igual a arr2[] intercambiando arr1[ 1] y arr1[3].

Entrada: arr1[] = {1, 0, 1}, arr2[] = {0, 1, 0}
Salida: No

Planteamiento: La idea para resolver este problema se basa en las siguientes observaciones: 

• La operación no cambia la frecuencia del número de unos y ceros en el arreglo arr1[] , por lo que si el número de 0 o 1 es diferente entre los arreglos, nunca podrán volverse iguales a la operación anterior.
• Si algún prefijo de arr2[] contiene más 1 que el prefijo de arr1[] de la misma longitud, entonces no es posible hacer que arr1[] y arr2[] sean iguales, ya que 1 solo se puede desplazar hacia la derecha.
• De lo contrario, en todos los demás casos, las arrays se pueden hacer iguales.

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar con 0 , para almacenar las diferencias de la suma del prefijo de arr1[] y arr2[] .
• Cuente el número de 1 y 0 en ambas arrays y compruebe si el número de 1 y 0 en arr1 [] no es igual al número de 1 y 0 en arr2[] y luego imprima “No” .
• Itere sobre el rango [1, N – 1] usando la variable i y haga lo siguiente:
  • Agregue el valor (arr1[i] – arr2[i]) a la variable cuenta .
  • Si el valor de count es menor que 0 , imprima «No» , de lo contrario, continúe con el siguiente par de elementos.
• Después de completar los pasos anteriores, si el recuento no es negativo en ningún paso, imprima «Sí» .

A continuación se muestra la implementación del enfoque anterior:

// 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 0
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) {
        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 Code
int 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 program for the above approach
import 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 Code
public 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.

# 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 0
def 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 Code
if __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# program for the above approach
using 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.

<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 0
function 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 arrays
var arr1 = [ 0, 1, 1, 0 ];
var arr2 = [ 0, 0, 1, 1 ];
 
// Size of the array
var N = arr1.length;
 
// Function Call
canMakeEqual(arr1, arr2, N);
 
// This code is contributed by rutvik_56
 
</script>

Yes

Complejidad temporal: O(N)
Espacio auxiliar: O(1)