Array binaria después de operaciones de alternancia de rango M

Considere una array binaria que consta de N elementos (inicialmente, todos los elementos son 0). Después de eso, recibe comandos M donde cada comando tiene la forma ab, lo que significa que debe cambiar todos los elementos de la array en el rango de a a b (ambos inclusive). Después de la ejecución de todos los comandos M, debe encontrar la array resultante.

Ejemplos: 

Input : N = 5, M = 3
        C1 = 1 3, C2 = 4 5, C3 = 1 4
Output : Resultant array = {0, 0, 0, 0, 1} 
Explanation :
Initial array : {0, 0, 0, 0, 0}
After first toggle : {1, 1, 1, 0, 0}
After second toggle : {1, 1, 1, 1, 1}
After third toggle :  {0, 0, 0, 0, 1}

Input : N = 5, M = 5
        C1 = 1 5, C2 = 1 5, C3 = 1 5,
        C4 = 1 5, C5 = 1 5
Output : Resultant array = {1, 1, 1, 1, 1} 

Enfoque ingenuo: para el N dado, debemos crear una array bool de n + 1 elementos y para cada uno de los comandos M tenemos que iterar de a a b y alternar todos los elementos en el rango de a a b con la ayuda de XOR. 

La complejidad de este enfoque es O(n^2) .  

for (int i = 1; i > a >> b;
    for (int j = a; j <= b; j++)
        arr[j] ^= 1;

Enfoque eficiente: la idea se basa en el problema de muestra analizado en el artículo Prefix Sum Array . Para el n dado, creamos una array bool de n+2 elementos y para cada uno de los comandos M, solo tenemos que alternar los elementos a y b+1 con la ayuda de XOR. Después de todos los comandos, procesaremos la array como arr[i] ^= arr[i-1]; 

La complejidad de este enfoque es O(n). 

Implementación:

// CPP program to find modified array after
// m range toggle operations.
#include<bits/stdc++.h>
using namespace std;
 
// function for toggle
void command(bool arr[], int a, int b)
{
    arr[a] ^= 1;
    arr[b+1] ^= 1;
}
 
// function for final processing of array
void process(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}
 
// function for printing result
void result(bool arr[], int n)
{
    for (int k=1; k<=n; k++)
        cout << arr[k] <<" ";
}
 
// driver program
int main()
{
    int n = 5, m = 3;
    bool arr[n+2] = {0};
 
    // function call for toggle
    command(arr, 1, 5);
    command(arr, 2, 5);
    command(arr, 3, 5);
     
    // process array
    process(arr, n);
     
    // print result
    result(arr, n);
    return 0;
}

// Java program to find modified array
// after m range toggle operations.
class GFG
{
 
// function for toggle
static void command(boolean arr[],
                    int a, int b)
{
    arr[a] ^= true;
    arr[b + 1] ^= true;
}
 
// function for final processing of array
static void process(boolean arr[], int n)
{
    for (int k = 1; k <= n; k++)
    {
        arr[k] ^= arr[k - 1];
    }
}
 
// function for printing result
static void result(boolean arr[], int n)
{
    for (int k = 1; k <= n; k++)
    {
        if(arr[k] == true)
            System.out.print("1" + " ");
        else
            System.out.print("0" + " ");
    }
}
 
// Driver Code
public static void main(String args[])
{
    int n = 5, m = 3;
    boolean arr[] = new boolean[n + 2];
 
    // function call for toggle
    command(arr, 1, 5);
    command(arr, 2, 5);
    command(arr, 3, 5);
 
    // process array
    process(arr, n);
 
    // print result
    result(arr, n);
}
}
 
// This code is contributed
// by PrinciRaj1992

# Python 3 program to find modified array after
# m range toggle operations.
 
# function for toggle
def command(brr, a, b):
    arr[a] ^= 1
    arr[b+1] ^= 1
 
# function for final processing of array
def process(arr, n):
    for k in range(1, n + 1, 1):
        arr[k] ^= arr[k - 1]
 
# function for printing result
def result(arr, n):
    for k in range(1, n + 1, 1):
        print(arr[k], end = " ")
 
# Driver Code
if __name__ == '__main__':
    n = 5
    m = 3
    arr = [0 for i in range(n+2)]
 
    # function call for toggle
    command(arr, 1, 5)
    command(arr, 2, 5)
    command(arr, 3, 5)
     
    # process array
    process(arr, n)
     
    # print result
    result(arr, n)
 
# This code is contributed by
# Surendra_Gangwar

// C# program to find modified array
// after m range toggle operations.
using System;
 
class GFG
{
 
// function for toggle
static void command(bool[] arr,
                    int a, int b)
{
    arr[a] ^= true;
    arr[b + 1] ^= true;
}
 
// function for final processing of array
static void process(bool[] arr, int n)
{
    for (int k = 1; k <= n; k++)
    {
        arr[k] ^= arr[k - 1];
    }
}
 
// function for printing result
static void result(bool[] arr, int n)
{
    for (int k = 1; k <= n; k++)
    {
        if(arr[k] == true)
            Console.Write("1" + " ");
        else
            Console.Write("0" + " ");
    }
}
 
// Driver Code
public static void Main()
{
    int n = 5, m = 3;
    bool[] arr = new bool[n + 2];
 
    // function call for toggle
    command(arr, 1, 5);
    command(arr, 2, 5);
    command(arr, 3, 5);
 
    // process array
    process(arr, n);
 
    // print result
    result(arr, n);
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program to find modified array
// after m range toggle operations.
 
// function for toggle
function command($arr, $a, $b)
{
    $arr[$a] = $arr[$a] ^ 1;
    $arr[$b + 1] ^= 1;
}
 
// function for final processing
// of array
function process($arr, $n)
{
    for ($k = 1; $k <= $n; $k++)
    {
        $arr[$k] = $arr[$k] ^ $arr[$k - 1];
    }
}
 
// function for printing result
function result($arr, $n)
{
    for ($k = 1; $k <= $n; $k++)
    echo $arr[$k] . " ";
}
 
// Driver Code
$n = 5; $m = 3;
$arr = new SplFixedArray(7);
$arr[6] = array(0);
 
// function call for toggle
command($arr, 1, 5);
command($arr, 2, 5);
command($arr, 3, 5);
 
// process array
process($arr, $n);
 
// print result
result($arr, $n);
 
// This code is contributed
// by Mukul Singh
?>

<script>
 
// Javascript program to find modified array after
// m range toggle operations.
 
// function for toggle
function command(arr, a, b)
{
    arr[a] ^= 1;
    arr[b+1] ^= 1;
}
 
// function for final processing of array
function process( arr, n)
{
    for (var k=1; k<=n; k++)
        arr[k] ^= arr[k-1];
}
 
// function for printing result
function result( arr, n)
{
    for (var k=1; k<=n; k++)
        document.write( arr[k] + " ");
}
 
// driver program
var n = 5, m = 3;
var arr = Array(n+2).fill(0);
// function call for toggle
command(arr, 1, 5);
command(arr, 2, 5);
command(arr, 3, 5);
 
// process array
process(arr, n);
 
// print result
result(arr, n);
 
 
</script>

1 0 1 1 1 

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

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.