Dada una array, arr[] de N enteros positivos y M consultas que constan de dos enteros [L i , R i ] donde 1 ≤ Li ≤ Ri ≤ N . Para cada consulta, encuentre el número de subarreglos en el rango [L i , R i ] para los cuales (X+1)=(X⊕1) donde X denota el xor de un subarreglo.
Entrada: arr[]= {1, 2, 9, 8, 7}, queries[] = {{1, 5}, {3, 4}}
Salida: 6 1
Explicación:
Consulta 1: L=1, R= 5: subarreglos [1, 3], [1, 4], [2, 2], [2, 5], [3, 5], [4, 4]
Consulta 2: L=3, R=4: subarreglo [4, 4]Entrada: arr[] = {1, 2, 2, 4, 5}, consultas[] = {{2, 4}, {3, 5}}
Salida: 6 3
Enfoque ingenuo: para cada consulta, seleccione el rango dado [L i , R i ] y para cada subarreglo verifique si satisface la condición dada.
Complejidad del tiempo: O(N 3 * M)
Enfoque eficiente: En el problema anterior, se pueden hacer las siguientes observaciones:
- Para satisfacer la condición dada, X debe ser un número par porque
- Si X es par, ( X ⊕1)=( X +1)
- Si X es impar, ( X ⊕1)=( X −1)
- Para un subarreglo, su xor será par si el conteo de números impares en ese subarreglo es par.
- Si el conteo de números impares es par, entonces la suma del subarreglo será par. Entonces, los subarreglos con una suma par son la respuesta a este problema.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
vector<int> countXorSubarr(
vector<int> arr,
vector<vector<int> > queries,
int n, int m)
{
// As queries are in 1-based indexing,
// add one dummy entry in beginning
// of arr to make it 1-indexed
arr.insert(arr.begin(), 0);
// sum[] will contain parity
// of prefix sum till index i
// count[] will contain
// number of 0s in sum[]
int count[n + 1], sum[n + 1];
count[0] = sum[0] = 0;
for (int i = 1; i <= n; i++) {
// Take the parity of current sum
sum[i] = (sum[i - 1] + arr[i]) % 2;
count[i] = count[i - 1];
// If current parity is even,
// increase the count
if (sum[i] % 2 == 0)
count[i]++;
}
// Array to hold the answer of 'm' queries
vector<int> ans;
// Iterate through queries and use handshake
// lemma to count even sum subarrays
// ( Note that an even sum can
// be formed by two even or two odd )
for (vector<int> qu : queries) {
int L = qu[0], R = qu[1];
// Find count of even and
// odd sums in range [L, R]
int even = count[R] - count[L - 1];
int odd = (R - L + 1) - even;
// If prefix sum at L-1 is odd,
// then we need to swap
// our counts of odd and even
if (sum[L - 1] == 1)
swap(even, odd);
// Taking no element is also
// considered an even sum
// so even will be increased by 1
// (This is the condition when
// a prefix of even sum is taken)
even++;
// Find number of ways to
// select two even's or two odd's
int subCount = (even * (even - 1)) / 2
+ (odd * (odd - 1)) / 2;
ans.push_back(subCount);
}
return ans;
}
// Driver code
int main()
{
int n = 5;
vector<int> arr = { 1, 2, 9, 8, 7 };
int m = 2;
vector<vector<int> > queries
= { { 1, 5 }, { 3, 4 } };
// Function call and print answer
vector<int> ans
= countXorSubarr(arr, queries, n, m);
for (int x : ans)
cout << x << " ";
cout << endl;
return 0;
}
Java
// Java program for the above approach
import java.util.ArrayList;
class GFG
{
public static ArrayList<Integer> countXorSubarr(int[] arr, int[][] queries, int n, int m) {
// As queries are in 1-based indexing,
// add one dummy entry in beggining
// of arr to make it 1-indexed
// arr.insert(arr.begin(), 0);
int[] temp_arr = new int[arr.length + 1];
temp_arr[0] = 0;
for (int i = 1; i < temp_arr.length; i++) {
temp_arr[i] = arr[i - 1];
}
arr = temp_arr.clone();
// sum[] will contain parity
// of prefix sum till index i
// count[] will contain
// number of 0s in sum[]
int[] count = new int[n + 1];
int[] sum = new int[n + 1];
count[0] = sum[0] = 0;
for (int i = 1; i <= n; i++) {
// Take the parity of current sum
sum[i] = (sum[i - 1] + arr[i]) % 2;
count[i] = count[i - 1];
// If current parity is even,
// increase the count
if (sum[i] % 2 == 0)
count[i]++;
}
// Array to hold the answer of 'm' queries
ArrayList<Integer> ans = new ArrayList<Integer>();
// Iterate through queries and use handshake
// lemma to count even sum subarrays
// ( Note that an even sum can
// be formed by two even or two odd )
for (int[] qu : queries) {
int L = qu[0], R = qu[1];
// Find count of even and
// odd sums in range [L, R]
int even = count[R] - count[L - 1];
int odd = (R - L + 1) - even;
// If prefix sum at L-1 is odd,
// then we need to swap
// our counts of odd and even
if (sum[L - 1] == 1) {
int temp = even;
even = odd;
odd = temp;
}
// Taking no element is also
// considered an even sum
// so even will be increased by 1
// (This is the condition when
// a prefix of even sum is taken)
even++;
// Find number of ways to
// select two even's or two odd's
int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;
ans.add(subCount);
}
return ans;
}
// Driver code
public static void main(String args[])
{
int n = 5;
int[] arr = { 1, 2, 9, 8, 7 };
int m = 2;
int[][] queries = { { 1, 5 }, { 3, 4 } };
// Function call and print answer
ArrayList<Integer> ans = countXorSubarr(arr, queries, n, m);
for (int x : ans)
System.out.print(x + " ");
System.out.println("");
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python program for the above approach import math def countXorSubarr(arr, queries, n, m): # As queries are in 1-based indexing, # add one dummy entry in beggining # of arr to make it 1-indexed arr.insert(0, 0) # sum[] will contain parity # of prefix sum till index i # count[] will contain # number of 0s in sum[] count = [0 for _ in range(n + 1)] sum = [0 for _ in range(n + 1)] for i in range(1, n+1): # Take the parity of current sum sum[i] = (sum[i - 1] + arr[i]) % 2 count[i] = count[i - 1] # If current parity is even, # increase the count if (sum[i] % 2 == 0): count[i] += 1 # Array to hold the answer of 'm' queries ans = [] # Iterate through queries and use handshake # lemma to count even sum subarrays # ( Note that an even sum can # be formed by two even or two odd ) for qu in queries: L = qu[0] R = qu[1] # Find count of even and # odd sums in range [L, R] even = count[R] - count[L - 1] odd = (R - L + 1) - even # If prefix sum at L-1 is odd, # then we need to swap # our counts of odd and even if (sum[L - 1] == 1): temp = even even = odd odd = temp # Taking no element is also # considered an even sum # so even will be increased by 1 # (This is the condition when # a prefix of even sum is taken) even += 1 # Find number of ways to # select two even's or two odd's subCount = (even * (even - 1)) // 2 + (odd * (odd - 1)) // 2 ans.append(subCount) return ans # Driver code if __name__ == "__main__": n = 5 arr = [1, 2, 9, 8, 7] m = 2 queries = [[1, 5], [3, 4]] # Function call and print answer ans = countXorSubarr(arr, queries, n, m) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
public static List<int> countXorSubarr(int[] arr, int[,] queries, int n, int m)
{
// As queries are in 1-based indexing,
// add one dummy entry in beggining
// of arr to make it 1-indexed
// arr.insert(arr.begin(), 0);
int[] temp_arr = new int[arr.Length + 1];
temp_arr[0] = 0;
for (int i = 1; i < temp_arr.Length; i++) {
temp_arr[i] = arr[i - 1];
}
arr = temp_arr;
// sum[] will contain parity
// of prefix sum till index i
// []count will contain
// number of 0s in sum[]
int[] count = new int[n + 1];
int[] sum = new int[n + 1];
count[0] = sum[0] = 0;
for (int i = 1; i <= n; i++) {
// Take the parity of current sum
sum[i] = (sum[i - 1] + arr[i]) % 2;
count[i] = count[i - 1];
// If current parity is even,
// increase the count
if (sum[i] % 2 == 0)
count[i]++;
}
// Array to hold the answer of 'm' queries
List<int> ans = new List<int>();
// Iterate through queries and use handshake
// lemma to count even sum subarrays
// ( Note that an even sum can
// be formed by two even or two odd )
for(int i = 0; i < queries.GetLength(0); i++)
{
int L = queries[i,0], R = queries[i,1];
// Find count of even and
// odd sums in range [L, R]
int even = count[R] - count[L - 1];
int odd = (R - L + 1) - even;
// If prefix sum at L-1 is odd,
// then we need to swap
// our counts of odd and even
if (sum[L - 1] == 1) {
int temp = even;
even = odd;
odd = temp;
}
// Taking no element is also
// considered an even sum
// so even will be increased by 1
// (This is the condition when
// a prefix of even sum is taken)
even++;
// Find number of ways to
// select two even's or two odd's
int subCount = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2;
ans.Add(subCount);
}
return ans;
}
public static int[] GetRow(int[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver code
public static void Main(String []args)
{
int n = 5;
int[] arr = { 1, 2, 9, 8, 7 };
int m = 2;
int[,] queries = { { 1, 5 }, { 3, 4 } };
// Function call and print answer
List<int> ans = countXorSubarr(arr, queries, n, m);
foreach (int x in ans)
Console.Write(x + " ");
Console.WriteLine("");
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
function countXorSubarr(arr, queries, n, m)
{
// sum[] will contain parity
// of prefix sum till index i
// count[] will contain
// number of 0s in sum[]
let count = new Array(n + 1), sum = new Array(n + 1);
count[0] = sum[0] = 0;
for (let i = 1; i <= n; i++) {
// Take the parity of current sum
sum[i] = (sum[i - 1] + arr[i - 1]) % 2;
count[i] = count[i - 1];
// If current parity is even,
// increase the count
if (sum[i] % 2 == 0)
count[i]++;
}
// Array to hold the answer of 'm' queries
let ans = [];
// Iterate through queries and use handshake
// lemma to count even sum subarrays
// ( Note that an even sum can
// be formed by two even or two odd )
for (let qu of queries) {
let L = qu[0], R = qu[1];
// Find count of even and
// odd sums in range [L, R]
let even = count[R] - count[L - 1];
let odd = (R - L + 1) - even;
// If prefix sum at L-1 is odd,
// then we need to swap
// our counts of odd and even
if (sum[L - 1] == 1) {
temp = even
even = odd
odd = temp
}
// Taking no element is also
// considered an even sum
// so even will be increased by 1
// (This is the condition when
// a prefix of even sum is taken)
even++;
// Find number of ways to
// select two even's or two odd's
let subCount = (even * (even - 1)) / 2
+ (odd * (odd - 1)) / 2;
ans.push(subCount);
}
return ans;
}
// Driver code
let n = 5;
let arr = [1, 2, 9, 8, 7];
let m = 2;
let queries
= [[1, 5], [3, 4]];
// Function call and print answer
let ans
= countXorSubarr(arr, queries, n, m);
for (let x of ans)
document.write(x + " ");
// This code is contributed by Potta Lokesh
</script>
Producción
6 1
Complejidad temporal: O(N+M)
Espacio auxiliar: O(N+M)
Publicación traducida automáticamente
Artículo escrito por himanshu77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA