Dada una array de N números. La tarea es maximizar la cantidad de subarreglos con valor XOR cero intercambiando los bits de un elemento de array de cualquier subarreglo dado cualquier número de veces.
Nota: 1<=A[i]<=10 18
Ejemplos:
Entrada: a[] = {6, 7, 14}
Salida: 2
2 subarreglos son {7, 14} y {6, 7 y 14} intercambiando sus bits individualmente en subarreglos.
El subarreglo {7, 14} es válido ya que 7 se cambia a 11 (111 a 1011) y 14 se cambia a 11, por lo que el subarreglo es {11, 11} ahora. El subarreglo {6, 7, 14} es válido ya que 6 se cambia a 3 y 7 a 13 y 14 no cambia, por lo que 3^13^14 = 0.
Entrada: a[] = {1, 1}
Salida:
Enfoque: la primera observación es que solo un número par de bits establecidos en cualquier índice dado puede llevar a un valor XOR de 0. Dado que el tamaño máximo de los elementos de la array puede ser del orden de 10 18 , podemos suponer 60 bits para el intercambio. Se pueden seguir los siguientes pasos para resolver el problema anterior:
- Dado que solo se requiere el número de bits establecidos, cuente el número de bits establecidos en cada i-ésimo elemento.
- Hay dos condiciones que deben cumplirse simultáneamente para que el XOR de cualquier subarreglo sea cero mediante el intercambio de bits. Las condiciones son las siguientes:
- Si hay incluso una cantidad de bits establecidos en cualquier rango LR, entonces podemos intentar hacer el XOR del subarreglo 0.
- Si la suma de los bits es menor o igual al doble de la mayor cantidad de bits establecidos en cualquier rango dado, entonces es posible hacer que su XOR sea cero.
El trabajo matemático que debe realizarse en el rango LR para cada subarreglo se ha explicado anteriormente.
Una solución ingenua será iterar para cada subarreglo y verificar ambas condiciones explícitamente y contar el número de tales subarreglos. Pero la complejidad del tiempo al hacerlo será O (N ^ 2).
Una solución eficiente será seguir los pasos mencionados a continuación:
- Utilice prefix[] sum array para calcular el número de subarreglos que obedecen solo a la primera condición.
- El paso 1 nos da el número de subarreglos que es una suma de bits incluso en complejidad O(N) .
- Usando el principio de inclusión-exclusión , podemos restar explícitamente el número de subarreglos cuyo 2*mayor número de bits establecidos en el subarreglo excede la suma de los bits establecidos en el subarreglo.
- Usando las matemáticas, podemos reducir la cantidad de verificación de subarreglo en el Paso 3, ya que la cantidad de bits establecidos puede ser un mínimo de 1, solo podemos verificar cada subarreglo de longitud 60 , ya que más allá de esa longitud, la segunda condición nunca puede ser falsificado.
- Una vez hecho esto, podemos restar el número del número de subarreglos obtenidos en el Paso 1 para obtener nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int exclude(int a[], int n)
{
int count = 0;
// iterate in the array
for (int i = 0; i < n; i++) {
// store the sum of set bits
// in the subarray
int s = 0;
int maximum = 0;
// iterate for range of 60 subarrays
for (int j = i; j < min(n, i + 60); j++) {
s += a[j];
maximum = max(a[j], maximum);
// check if falsifies the condition-2
if (s % 2 == 0 && 2 * maximum > s)
count++;
}
}
return count;
}
// Function to count subarrays
int countSubarrays(int a[], int n)
{
// replace the array element by number
// of set bits in them
for (int i = 0; i < n; i++)
a[i] = __builtin_popcountll(a[i]);
// calculate prefix array
int pre[n];
for (int i = 0; i < n; i++) {
pre[i] = a[i];
if (i != 0)
pre[i] += pre[i - 1];
}
// Count the number of subarrays
// satisfying step-1
int odd = 0, even = 0;
// count number of odd and even
for (int i = 0; i < n; i++) {
if (pre[i] & 1)
odd++;
}
even = n - odd;
// Increase even by 1 for 1, so that the
// subarrays starting from the index-0
// are also taken to count
even++;
// total subarrays satisfying condition-1 only
int answer = (odd * (odd - 1) / 2) + (even * (even - 1) / 2);
cout << answer << endl;
// exclude total subarrays not satisfying condition2
answer = answer - exclude(a, n);
return answer;
}
// Driver Code
int main()
{
int a[] = { 6, 7, 14 };
int n = sizeof(a) / sizeof(a[0]);
cout << countSubarrays(a, n);
return 0;
}
Java
// Java Program to find the minimum element to
// be added such that the array can be partitioned
// into two contiguous subarrays with equal sums
import java.util.*;
class GFG
{
// Function to count subarrays not satisfying condition 2
static int exclude(int a[], int n)
{
int count = 0;
// iterate in the array
for (int i = 0; i < n; i++)
{
// store the sum of set bits
// in the subarray
int s = 0;
int maximum = 0;
// iterate for range of 60 subarrays
for (int j = i; j < Math.min(n, i + 60); j++)
{
s += a[j];
maximum = Math.max(a[j], maximum);
// check if falsifies the condition-2
if (s % 2 == 0 && 2 * maximum > s)
count++;
}
}
return count;
}
// Function to count subarrays
static int countSubarrays(int a[], int n)
{
// replace the array element by number
// of set bits in them
for (int i = 0; i < n; i++)
a[i] = Integer.bitCount(a[i]);
// calculate prefix array
int []pre = new int[n];
for (int i = 0; i < n; i++)
{
pre[i] = a[i];
if (i != 0)
pre[i] += pre[i - 1];
}
// Count the number of subarrays
// satisfying step-1
int odd = 0, even = 0;
// count number of odd and even
for (int i = 0; i < n; i++)
{
if (pre[i]%2== 1)
odd++;
}
even = n - odd;
// Increase even by 1 for 1, so that the
// subarrays starting from the index-0
// are also taken to count
even++;
// total subarrays satisfying condition-1 only
int answer = (odd * (odd - 1) / 2) + (even * (even - 1) / 2);
System.out.println(answer);
// exclude total subarrays not satisfying condition2
answer = answer - exclude(a, n);
return answer;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 6, 7, 14 };
int n = a.length;
System.out.println(countSubarrays(a, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 code for the given approach.
# Function to count subarrays not
# satisfying condition 2
def exclude(a, n):
count = 0
# iterate in the array
for i in range(0, n):
# store the sum of set bits
# in the subarray
s = 0
maximum = 0
# iterate for range of 60 subarrays
for j in range(i, min(n, i + 60)):
s += a[j]
maximum = max(a[j], maximum)
# check if falsifies the condition-2
if s % 2 == 0 and 2 * maximum > s:
count += 1
return count
# Function to count subarrays
def countSubarrays(a, n):
# replace the array element by
# number of set bits in them
for i in range(0, n):
a[i] = bin(a[i]).count('1')
# calculate prefix array
pre = [None] * n
for i in range(0, n):
pre[i] = a[i]
if i != 0:
pre[i] += pre[i - 1]
# Count the number of subarrays
# satisfying step-1
odd, even = 0, 0
# count number of odd and even
for i in range(0, n):
if pre[i] & 1:
odd += 1
even = n - odd
# Increase even by 1 for 1, so that the
# subarrays starting from the index-0
# are also taken to count
even += 1
# total subarrays satisfying condition-1 only
answer = ((odd * (odd - 1) // 2) +
(even * (even - 1) // 2))
print(answer)
# exclude total subarrays not
# satisfying condition2
answer = answer - exclude(a, n)
return answer
# Driver Code
if __name__ == "__main__":
a = [6, 7, 14]
n = len(a)
print(countSubarrays(a, n))
# This code is contributed by Rituraj Jain
C#
// C# Program to find the minimum element to
// be added such that the array can be partitioned
// into two contiguous subarrays with equal sums
using System;
class GFG
{
// Function to count subarrays not satisfying condition 2
static int exclude(int []a, int n)
{
int count = 0;
// iterate in the array
for (int i = 0; i < n; i++)
{
// store the sum of set bits
// in the subarray
int s = 0;
int maximum = 0;
// iterate for range of 60 subarrays
for (int j = i; j < Math.Min(n, i + 60); j++)
{
s += a[j];
maximum = Math.Max(a[j], maximum);
// check if falsifies the condition-2
if (s % 2 == 0 && 2 * maximum > s)
count++;
}
}
return count;
}
// Function to count subarrays
static int countSubarrays(int []a, int n)
{
// replace the array element by number
// of set bits in them
for (int i = 0; i < n; i++)
a[i] = bitCount(a[i]);
// calculate prefix array
int []pre = new int[n];
for (int i = 0; i < n; i++)
{
pre[i] = a[i];
if (i != 0)
pre[i] += pre[i - 1];
}
// Count the number of subarrays
// satisfying step-1
int odd = 0, even = 0;
// count number of odd and even
for (int i = 0; i < n; i++)
{
if (pre[i]%2== 1)
odd++;
}
even = n - odd;
// Increase even by 1 for 1, so that the
// subarrays starting from the index-0
// are also taken to count
even++;
// total subarrays satisfying condition-1 only
int answer = (odd * (odd - 1) / 2) + (even * (even - 1) / 2);
Console.WriteLine(answer);
// exclude total subarrays not satisfying condition2
answer = answer - exclude(a, n);
return answer;
}
static int bitCount(long x)
{
int setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 6, 7, 14 };
int n = a.Length;
Console.WriteLine(countSubarrays(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Function to count subarrays not
// satisfying condition 2
function exclude(a, n)
{
let count = 0;
// iterate in the array
for (let i = 0; i < n; i++)
{
// store the sum of set bits
// in the subarray
let s = 0;
let maximum = 0;
// iterate for range of 60 subarrays
for (let j = i; j < Math.min(n, i + 60); j++)
{
s += a[j];
maximum = Math.max(a[j], maximum);
// check if falsifies the condition-2
if (s % 2 == 0 && 2 * maximum > s)
count++;
}
}
return count;
}
// Function to count subarrays
function countSubarrays(a, n)
{
// replace the array element by number
// of set bits in them
for (let i = 0; i < n; i++)
a[i] = bitCount(a[i]);
// calculate prefix array
let pre = new Array(n);
for (let i = 0; i < n; i++) {
pre[i] = a[i];
if (i != 0)
pre[i] += pre[i - 1];
}
// Count the number of subarrays
// satisfying step-1
let odd = 0, even = 0;
// count number of odd and even
for (let i = 0; i < n; i++) {
if (pre[i] & 1)
odd++;
}
even = n - odd;
// Increase even by 1 for 1, so that the
// subarrays starting from the index-0
// are also taken to count
even++;
// total subarrays satisfying condition-1 only
let answer = parseInt((odd * (odd - 1) / 2) +
(even * (even - 1) / 2));
document.write(answer + "<br>");
// exclude total subarrays not
// satisfying condition2
answer = answer - exclude(a, n);
return answer;
}
function bitCount(x)
{
let setBits = 0;
while (x != 0) {
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver Code
let a = [ 6, 7, 14 ];
let n = a.length;
document.write(countSubarrays(a, n));
</script>
Producción:
3 2
Complejidad de tiempo : O (N * 60), ya que estamos usando un bucle para atravesar N * 60 veces.
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para la array previa .