Binary array after M range toggle operations

Consider a binary array consisting of N elements (initially all elements are 0). After that, you are given M commands where each command is of form a b, which means you have to toggle all the elements of the array in range a to b (both inclusive). After the execution of all M commands, you have to find the resultant array.

Examples: 

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} 

Naive Approach: For the given N we should create a bool array of n+1 elements and for each of M commands we have to iterate from a to b and toggle all elements in the range of a to b with help of XOR. 

The complexity of this approach is O(n^2).  

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

Efficient Approach: The idea is based on the sample problem discussed in the Prefix Sum Array article. For the given n, we create a bool array of n+2 elements and for each of M commands, we have to just toggle elements a and b+1 with help of XOR. After all commands we will process the array as arr[i] ^= arr[i-1]; 

The complexity of this approach is O(n). 

Implementation:

// 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 

Time Complexity: O(n)
Auxiliary Space: O(1)