Dada una array ‘arr’, la tarea es encontrar todos los enteros posibles, cada uno de los cuales es el AND bit a bit de al menos una sub-array no vacía de ‘arr’.
Ejemplos:
Input: arr = {11, 15, 7, 19}
Output: [3, 19, 7, 11, 15]
3 = arr[2] AND arr[3]
19 = arr[3]
7 = arr[2]
11 = arr[0]
15 = arr[1]
Input: arr = {5, 2, 8, 4, 1}
Output: [0, 1, 2, 4, 5, 8]
0 = arr[3] AND arr[4]
1 = arr[4]
2 = arr[1]
4 = arr[3]
5 = arr[0]
8 = arr[2]
Enfoque ingenuo:
- Una array de tamaño ‘N’ contiene N*(N+1)/2 sub-arrays. Entonces, para una ‘N’ pequeña, itere sobre todos los subconjuntos posibles y agregue cada uno de sus resultados AND a un conjunto.
- Dado que los conjuntos no contienen duplicados, almacenará cada valor solo una vez.
- Finalmente, imprima el contenido del conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int main()
{
int A[] = {11, 15, 7, 19};
int N = sizeof(A) / sizeof(A[0]);
// Set to store all possible AND values.
unordered_set<int> s;
int i, j, res;
// Starting index of the sub-array.
for (i = 0; i < N; ++i)
// Ending index of the sub-array.
for (j = i, res = INT_MAX; j < N; ++j)
{
res &= A[j];
// AND value is added to the set.
s.insert(res);
}
// The set contains all possible AND values.
for (int i : s)
cout << i << " ";
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java implementation of the approach
import java.util.HashSet;
class CP {
public static void main(String[] args)
{
int[] A = { 11, 15, 7, 19 };
int N = A.length;
// Set to store all possible AND values.
HashSet<Integer> set = new HashSet<>();
int i, j, res;
// Starting index of the sub-array.
for (i = 0; i < N; ++i)
// Ending index of the sub-array.
for (j = i, res = Integer.MAX_VALUE; j < N; ++j) {
res &= A[j];
// AND value is added to the set.
set.add(res);
}
// The set contains all possible AND values.
System.out.println(set);
}
}
Python3
# Python3 implementation of the approach A = [11, 15, 7, 19] N = len(A) # Set to store all possible AND values. Set = set() # Starting index of the sub-array. for i in range(0, N): # Ending index of the sub-array. res = 2147483647 # Integer.MAX_VALUE for j in range(i, N): res &= A[j] # AND value is added to the set. Set.add(res) # The set contains all possible AND values. print(Set) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class CP {
public static void Main(String[] args)
{
int[] A = {11, 15, 7, 19};
int N = A.Length;
// Set to store all possible AND values.
HashSet<int> set1 = new HashSet<int>();
int i, j, res;
// Starting index of the sub-array.
for (i = 0; i < N; ++i)
{
// Ending index of the sub-array.
for (j = i, res = int.MaxValue; j < N; ++j)
{
res &= A[j];
// AND value is added to the set.
set1.Add(res);
}
}
// displaying the values
foreach(int m in set1)
{
Console.Write(m + " ");
}
}
}
[3, 19, 7, 11, 15]
Complejidad del tiempo: O(N^2)
Enfoque eficiente: este problema se puede resolver de manera eficiente mediante el enfoque de divide y vencerás.
- Considere cada elemento de la array como un solo segmento. (paso ‘Dividir’)
- Agregue el valor AND de todos los subarreglos al conjunto.
- Ahora, para el paso de ‘conquistar’, siga fusionando subarreglos consecutivos y siga agregando los valores AND adicionales obtenidos durante la fusión.
- Continúe con el paso 4, hasta que se obtenga un solo segmento que contenga toda la array.
A continuación se muestra la implementación del enfoque anterior:
// Java implementation of the approach
import java.util.*;
public class CP {
static int ar[];
static int n;
// Holds all possible AND results
static HashSet<Integer> allPossibleAND;
// driver code
public static void main(String[] args)
{
ar = new int[] { 11, 15, 7, 19 };
n = ar.length;
allPossibleAND = new HashSet<>(); // initialization
divideThenConquer(0, n - 1);
System.out.println(allPossibleAND);
}
// recursive function which adds all
// possible AND results to 'allPossibleAND'
static Segment divideThenConquer(int l, int r)
{
// can't divide into
//further segments
if (l == r)
{
allPossibleAND.add(ar[l]);
// Therefore, return a segment
// containing this single element.
Segment ret = new Segment();
ret.leftToRight.add(ar[l]);
ret.rightToLeft.add(ar[l]);
return ret;
}
// can be further divided into segments
else {
Segment left
= divideThenConquer(l, (l + r) / 2);
Segment right
= divideThenConquer((l + r) / 2 + 1, r);
// Now, add all possible AND results,
// contained in these two segments
/* ********************************
This step may seem to be inefficient
and time consuming, but it is not.
Read the 'Analysis' block below for
further clarification.
*********************************** */
for (int itr1 : left.rightToLeft)
for (int itr2 : right.leftToRight)
allPossibleAND.add(itr1 & itr2);
// 'conquer' step
return mergeSegments(left, right);
}
}
// returns the resulting segment after
// merging segments 'a' and 'b'
// 'conquer' step
static Segment mergeSegments(Segment a, Segment b)
{
Segment res = new Segment();
// The resulting segment will have
// same prefix sequence as segment 'a'
res.copyLR(a.leftToRight);
// The resulting segment will have
// same suffix sequence as segment 'b'
res.copyRL(b.rightToLeft);
Iterator<Integer> itr;
itr = b.leftToRight.iterator();
while (itr.hasNext())
res.addToLR(itr.next());
itr = a.rightToLeft.iterator();
while (itr.hasNext())
res.addToRL(itr.next());
return res;
}
}
class Segment {
// These 'vectors' will always
// contain atmost 30 values.
ArrayList<Integer> leftToRight
= new ArrayList<>();
ArrayList<Integer> rightToLeft
= new ArrayList<>();
void addToLR(int value)
{
int lastElement
= leftToRight.get(leftToRight.size() - 1);
// value decreased after AND-ing with 'value'
if ((lastElement & value) < lastElement)
leftToRight.add(lastElement & value);
}
void addToRL(int value)
{
int lastElement
= rightToLeft.get(rightToLeft.size() - 1);
// value decreased after AND-ing with 'value'
if ((lastElement & value) < lastElement)
rightToLeft.add(lastElement & value);
}
// copies 'lr' to 'leftToRight'
void copyLR(ArrayList<Integer> lr)
{
Iterator<Integer> itr = lr.iterator();
while (itr.hasNext())
leftToRight.add(itr.next());
}
// copies 'rl' to 'rightToLeft'
void copyRL(ArrayList<Integer> rl)
{
Iterator<Integer> itr = rl.iterator();
while (itr.hasNext())
rightToLeft.add(itr.next());
}
}
[19, 3, 7, 11, 15]
Análisis:
La principal optimización de este algoritmo es darse cuenta de que cualquier elemento de array puede generar un máximo de 30 enteros distintos (ya que se necesitan 30 bits para contener 1e9). ¿¿Confundido?? Procedamos paso a paso.
Comencemos un subarreglo desde el i-ésimo elemento que es A[i]. Como los elementos subsiguientes son AND-ed con Ai, el resultado puede disminuir o permanecer igual (porque un bit nunca cambiará de ‘0’ a ‘1’ después de una operación AND).
En el peor de los casos, A[i] puede ser 2^31 – 1 (los 30 bits serán ‘1’). Como los elementos tienen AND, se pueden obtener como máximo 30 valores distintos porque solo un bit puede cambiar de ‘1’ a ‘0’ en el peor de los casos,
es decir, 1111111111111111111111111111111 => 1111111111111111111111111101111
Entonces, para cada operación de ‘fusión’, estos valores distintos se fusionan para formar otro conjunto que tiene como máximo 30 enteros.
Por lo tanto, la Complejidad de tiempo en el peor de los casos para cada fusión puede ser O(30 * 30) = O(900).
Complejidad de tiempo: O(900*N*logN).
PD: La complejidad del tiempo puede parecer demasiado alta, pero en la práctica, la complejidad real se encuentra alrededor de O(K*N*logN), donde K es mucho menor que 900. Esto se debe a que las longitudes del ‘prefijo’ y ‘ las arrays de sufijos son mucho menores cuando ‘l’ y ‘r’ están bastante cerca.
Publicación traducida automáticamente
Artículo escrito por sarthakmannaofficial y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA