Dada una array arr[] de N enteros y Q consultas, cada consulta tiene dos enteros L y R , la tarea es encontrar el elemento que tiene el máximo de bits establecidos en el rango L a R.
Nota: Si hay varios elementos que tienen un número máximo de bits establecidos, imprima el máximo de ellos.
Ejemplos:
Entrada: arr[] = {18, 9, 8, 15, 14, 5}, Q = {{1, 4}}
Salida: 15
Explicación:
Subarreglo – {9, 8, 15, 14}
Representación binaria de estos enteros –
9 => 1001 => Establecer bits = 2
8 => 1000 => Establecer bits = 1
15 => 1111 => Establecer bits = 4
14 => 1110 => Establecer bits = 3
Por lo tanto, el elemento con el máximo de bits establecidos es 15 .Entrada: arr[] = {18, 9, 8, 15, 14, 5}, Q = {{0, 2}}
Salida: 18
Explicación:
Subarreglo – {18, 9, 8}
Representación binaria de estos enteros –
18 => 10010 => Set Bits = 2
9 => 1001 => Set Bits = 2
8 => 1000 => Set Bits = 1
Por lo tanto, el elemento con un máximo de bits establecidos es un máximo de 18 y 9, que es 18.
Enfoque ingenuo: una solución simple es ejecutar un ciclo de L a R y calcular la cantidad de bits establecidos para cada elemento y encontrar el elemento máximo de bits establecidos de L a R para cada consulta.
Complejidad de tiempo : O(Q * N)
Complejidad de espacio auxiliar : O(1)
Enfoque eficiente: la idea es utilizar el árbol de segmentos , donde cada Node contiene dos valores, el elemento con el número máximo de bits establecidos y el recuento de los bits máximos establecidos.
- Representación de árboles de segmentos:
- Los Nodes hoja son los elementos de la array dada.
- Cada Node interno representa alguna fusión de los Nodes hoja. La fusión puede ser diferente para diferentes problemas. Para este problema, la fusión es el máximo de max_set_bits de hojas bajo un Node.
- Se utiliza una representación de array de árbol para representar árboles de segmento. Para cada Node en el índice i, el hijo izquierdo está en el índice 2*i+1 , el hijo derecho en 2*i+2 y el padre está en (i-1)/2 .
- Construcción del árbol de segmentos a partir de una array dada:
- Empezamos con un segmento arr[0 . . . n-1]. y cada vez que dividimos el segmento actual en dos mitades (si aún no se ha convertido en un segmento de longitud 1), y luego llamamos al mismo procedimiento en ambas mitades, y para cada uno de esos segmentos, almacenamos max_set_bits y el valor en el Node correspondiente.
- Los bits establecidos máximos para cualquier combinación de dos rangos serán los bits establecidos máximos del lado izquierdo o los bits establecidos máximos del lado derecho, cualquiera que sea el máximo se tendrá en cuenta.
- Finalmente, calcule la consulta de rango en el árbol de segmentos .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find
// maximum set bits value in a range
#include <bits/stdc++.h>
using namespace std;
// Structure to store two
// values in one node
struct Node {
int value;
int max_set_bits;
};
Node tree[4 * 10000];
// Function that returns the count
// of set bits in a number
int setBits(int x)
{
// Parity will store the
// count of set bits
int parity = 0;
while (x != 0) {
if (x & 1)
parity++;
x = x >> 1;
}
return parity;
}
// Function to build the segment tree
void buildSegmentTree(int a[], int index,
int beg, int end)
{
// Condition to check if there is
// only one element in the array
if (beg == end) {
tree[index].value = a[beg];
tree[index].max_set_bits
= setBits(a[beg]);
}
else {
int mid = (beg + end) / 2;
// If there are more than one elements,
// then recur for left and right subtrees
buildSegmentTree(a, 2 * index + 1,
beg, mid);
buildSegmentTree(a, 2 * index + 2,
mid + 1, end);
// Condition to check the maximum set
// bits is greater in two subtrees
if (tree[2 * index + 1].max_set_bits
> tree[2 * index + 2].max_set_bits) {
tree[index].max_set_bits
= tree[2 * index + 1]
.max_set_bits;
tree[index].value
= tree[2 * index + 1]
.value;
}
else if (tree[2 * index + 2].max_set_bits
> tree[2 * index + 1].max_set_bits) {
tree[index].max_set_bits
= tree[2 * index + 2]
.max_set_bits;
tree[index].value
= tree[2 * index + 2].value;
}
// Condition when maximum set bits
// are equal in both subtrees
else {
tree[index].max_set_bits
= tree[2 * index + 2]
.max_set_bits;
tree[index].value = max(
tree[2 * index + 2].value,
tree[2 * index + 1].value);
}
}
}
// Function to do the range query
// in the segment tree
Node query(int index, int beg,
int end, int l, int r)
{
Node result;
result.value
= result.max_set_bits = -1;
// If segment of this node is outside the given
// range, then return the minimum value.
if (beg > r || end < l)
return result;
// If segment of this node is a part of given
// range, then return the node of the segment
if (beg >= l && end <= r)
return tree[index];
int mid = (beg + end) / 2;
// If left segment of this node falls out of
// range, then recur in the right side of
// the tree
if (l > mid)
return query(2 * index + 2, mid + 1,
end, l, r);
// If right segment of this node falls out of
// range, then recur in the left side of
// the tree
if (r <= mid)
return query(2 * index + 1, beg,
mid, l, r);
// If a part of this segment overlaps with
// the given range
Node left = query(2 * index + 1, beg,
mid, l, r);
Node right = query(2 * index + 2, mid + 1,
end, l, r);
if (left.max_set_bits > right.max_set_bits) {
result.max_set_bits = left.max_set_bits;
result.value = left.value;
}
else if (right.max_set_bits > left.max_set_bits) {
result.max_set_bits = right.max_set_bits;
result.value = right.value;
}
else {
result.max_set_bits = left.max_set_bits;
result.value = max(right.value, left.value);
}
// Returns the value
return result;
}
// Driver code
int main()
{
int a[] = { 18, 9, 8, 15, 14, 5 };
// Calculates the length of array
int N = sizeof(a) / sizeof(a[0]);
// Build Segment Tree
buildSegmentTree(a, 0, 0, N - 1);
// Find the max set bits value between
// 1st and 4th index of array
cout << query(0, 0, N - 1, 1, 4).value
<< endl;
// Find the max set bits value between
// 0th and 2nd index of array
cout << query(0, 0, N - 1, 0, 2).value
<< endl;
return 0;
}
Java
// Java implementation to find
// maximum set bits value in a range
import java.util.*;
class GFG{
// Structure to store two
// values in one node
static class Node
{
int value;
int max_set_bits;
};
static Node []tree = new Node[4 * 10000];
// Function that returns the count
// of set bits in a number
static int setBits(int x)
{
// Parity will store the
// count of set bits
int parity = 0;
while (x != 0)
{
if (x % 2 == 1)
parity++;
x = x >> 1;
}
return parity;
}
// Function to build the segment tree
static void buildSegmentTree(int a[], int index,
int beg, int end)
{
// Condition to check if there is
// only one element in the array
if (beg == end)
{
tree[index].value = a[beg];
tree[index].max_set_bits = setBits(a[beg]);
}
else
{
int mid = (beg + end) / 2;
// If there are more than one elements,
// then recur for left and right subtrees
buildSegmentTree(a, 2 * index + 1,
beg, mid);
buildSegmentTree(a, 2 * index + 2,
mid + 1, end);
// Condition to check the maximum set
// bits is greater in two subtrees
if (tree[2 * index + 1].max_set_bits >
tree[2 * index + 2].max_set_bits)
{
tree[index].max_set_bits =
tree[2 * index + 1].max_set_bits;
tree[index].value =
tree[2 * index + 1].value;
}
else if (tree[2 * index + 2].max_set_bits >
tree[2 * index + 1].max_set_bits)
{
tree[index].max_set_bits =
tree[2 * index + 2].max_set_bits;
tree[index].value =
tree[2 * index + 2].value;
}
// Condition when maximum set bits
// are equal in both subtrees
else
{
tree[index].max_set_bits =
tree[2 * index + 2].max_set_bits;
tree[index].value = Math.max(
tree[2 * index + 2].value,
tree[2 * index + 1].value);
}
}
}
// Function to do the range query
// in the segment tree
static Node query(int index, int beg,
int end, int l, int r)
{
Node result = new Node();
result.value = result.max_set_bits = -1;
// If segment of this node is outside the given
// range, then return the minimum value.
if (beg > r || end < l)
return result;
// If segment of this node is a part of given
// range, then return the node of the segment
if (beg >= l && end <= r)
return tree[index];
int mid = (beg + end) / 2;
// If left segment of this node falls out of
// range, then recur in the right side of
// the tree
if (l > mid)
return query(2 * index + 2, mid + 1,
end, l, r);
// If right segment of this node falls out of
// range, then recur in the left side of
// the tree
if (r <= mid)
return query(2 * index + 1, beg,
mid, l, r);
// If a part of this segment overlaps with
// the given range
Node left = query(2 * index + 1, beg,
mid, l, r);
Node right = query(2 * index + 2, mid + 1,
end, l, r);
if (left.max_set_bits > right.max_set_bits)
{
result.max_set_bits = left.max_set_bits;
result.value = left.value;
}
else if (right.max_set_bits > left.max_set_bits)
{
result.max_set_bits = right.max_set_bits;
result.value = right.value;
}
else
{
result.max_set_bits = left.max_set_bits;
result.value = Math.max(right.value,
left.value);
}
// Returns the value
return result;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 18, 9, 8, 15, 14, 5 };
// Calculates the length of array
int N = a.length;
for(int i = 0; i < tree.length; i++)
tree[i] = new Node();
// Build Segment Tree
buildSegmentTree(a, 0, 0, N - 1);
// Find the max set bits value between
// 1st and 4th index of array
System.out.print(query(0, 0, N - 1, 1, 4).value +"\n");
// Find the max set bits value between
// 0th and 2nd index of array
System.out.print(query(0, 0, N - 1, 0, 2).value +"\n");
}
}
// This code is contributed by amal kumar choubey
Python3
# Python3 implementation to find # maximum set bits value in a range # Structure to store two # values in one node from typing import List class Node: def __init__(self) -> None: self.value = 0 self.max_set_bits = 0 tree = [Node() for _ in range(4 * 10000)] # Function that returns the count # of set bits in a number def setBits(x: int) -> int: # Parity will store the # count of set bits parity = 0 while (x != 0): if (x & 1): parity += 1 x = x >> 1 return parity # Function to build the segment tree def buildSegmentTree(a: List[int], index: int, beg: int, end: int) -> None: # Condition to check if there is # only one element in the array if (beg == end): tree[index].value = a[beg] tree[index].max_set_bits = setBits(a[beg]) else: mid = (beg + end) // 2 # If there are more than one elements, # then recur for left and right subtrees buildSegmentTree(a, 2 * index + 1, beg, mid) buildSegmentTree(a, 2 * index + 2, mid + 1, end) # Condition to check the maximum set # bits is greater in two subtrees if (tree[2 * index + 1].max_set_bits > tree[2 * index + 2].max_set_bits): tree[index].max_set_bits = tree[2 * index + 1].max_set_bits tree[index].value = tree[2 * index + 1].value elif (tree[2 * index + 2].max_set_bits > tree[2 * index + 1].max_set_bits): tree[index].max_set_bits = tree[2 * index + 2].max_set_bits tree[index].value = tree[2 * index + 2].value # Condition when maximum set bits # are equal in both subtrees else: tree[index].max_set_bits = tree[2 * index + 2].max_set_bits tree[index].value = max(tree[2 * index + 2].value, tree[2 * index + 1].value) # Function to do the range query # in the segment tree def query(index: int, beg: int, end: int, l: int, r: int) -> Node: result = Node() result.value = result.max_set_bits = -1 # If segment of this node is outside the given # range, then return the minimum value. if (beg > r or end < l): return result # If segment of this node is a part of given # range, then return the node of the segment if (beg >= l and end <= r): return tree[index] mid = (beg + end) // 2 # If left segment of this node falls out of # range, then recur in the right side of # the tree if (l > mid): return query(2 * index + 2, mid + 1, end, l, r) # If right segment of this node falls out of # range, then recur in the left side of # the tree if (r <= mid): return query(2 * index + 1, beg, mid, l, r) # If a part of this segment overlaps with # the given range left = query(2 * index + 1, beg, mid, l, r) right = query(2 * index + 2, mid + 1, end, l, r) if (left.max_set_bits > right.max_set_bits): result.max_set_bits = left.max_set_bits result.value = left.value elif (right.max_set_bits > left.max_set_bits): result.max_set_bits = right.max_set_bits result.value = right.value else: result.max_set_bits = left.max_set_bits result.value = max(right.value, left.value) # Returns the value return result # Driver code if __name__ == "__main__": a = [ 18, 9, 8, 15, 14, 5 ] # Calculates the length of array N = len(a) # Build Segment Tree buildSegmentTree(a, 0, 0, N - 1) # Find the max set bits value between # 1st and 4th index of array print(query(0, 0, N - 1, 1, 4).value) # Find the max set bits value between # 0th and 2nd index of array print(query(0, 0, N - 1, 0, 2).value) # This code is contributed by sanjeev2552
C#
// C# implementation to find maximum
// set bits value in a range
using System;
class GFG{
// Structure to store two
// values in one node
class Node
{
public int value;
public int max_set_bits;
};
static Node []tree = new Node[4 * 10000];
// Function that returns the count
// of set bits in a number
static int setBits(int x)
{
// Parity will store the
// count of set bits
int parity = 0;
while (x != 0)
{
if (x % 2 == 1)
parity++;
x = x >> 1;
}
return parity;
}
// Function to build the segment tree
static void buildSegmentTree(int []a, int index,
int beg, int end)
{
// Condition to check if there is
// only one element in the array
if (beg == end)
{
tree[index].value = a[beg];
tree[index].max_set_bits = setBits(a[beg]);
}
else
{
int mid = (beg + end) / 2;
// If there are more than one elements,
// then recur for left and right subtrees
buildSegmentTree(a, 2 * index + 1,
beg, mid);
buildSegmentTree(a, 2 * index + 2,
mid + 1, end);
// Condition to check the maximum set
// bits is greater in two subtrees
if (tree[2 * index + 1].max_set_bits >
tree[2 * index + 2].max_set_bits)
{
tree[index].max_set_bits =
tree[2 * index + 1].max_set_bits;
tree[index].value =
tree[2 * index + 1].value;
}
else if (tree[2 * index + 2].max_set_bits >
tree[2 * index + 1].max_set_bits)
{
tree[index].max_set_bits =
tree[2 * index + 2].max_set_bits;
tree[index].value =
tree[2 * index + 2].value;
}
// Condition when maximum set bits
// are equal in both subtrees
else
{
tree[index].max_set_bits =
tree[2 * index + 2].max_set_bits;
tree[index].value = Math.Max(
tree[2 * index + 2].value,
tree[2 * index + 1].value);
}
}
}
// Function to do the range query
// in the segment tree
static Node query(int index, int beg,
int end, int l, int r)
{
Node result = new Node();
result.value = result.max_set_bits = -1;
// If segment of this node is outside the given
// range, then return the minimum value.
if (beg > r || end < l)
return result;
// If segment of this node is a part of given
// range, then return the node of the segment
if (beg >= l && end <= r)
return tree[index];
int mid = (beg + end) / 2;
// If left segment of this node falls out of
// range, then recur in the right side of
// the tree
if (l > mid)
return query(2 * index + 2, mid + 1,
end, l, r);
// If right segment of this node falls out of
// range, then recur in the left side of
// the tree
if (r <= mid)
return query(2 * index + 1, beg,
mid, l, r);
// If a part of this segment overlaps with
// the given range
Node left = query(2 * index + 1, beg,
mid, l, r);
Node right = query(2 * index + 2, mid + 1,
end, l, r);
if (left.max_set_bits > right.max_set_bits)
{
result.max_set_bits = left.max_set_bits;
result.value = left.value;
}
else if (right.max_set_bits > left.max_set_bits)
{
result.max_set_bits = right.max_set_bits;
result.value = right.value;
}
else
{
result.max_set_bits = left.max_set_bits;
result.value = Math.Max(right.value,
left.value);
}
// Returns the value
return result;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 18, 9, 8, 15, 14, 5 };
// Calculates the length of array
int N = a.Length;
for(int i = 0; i < tree.Length; i++)
tree[i] = new Node();
// Build Segment Tree
buildSegmentTree(a, 0, 0, N - 1);
// Find the max set bits value between
// 1st and 4th index of array
Console.Write(query(0, 0, N - 1, 1, 4).value + "\n");
// Find the max set bits value between
// 0th and 2nd index of array
Console.Write(query(0, 0, N - 1, 0, 2).value + "\n");
}
}
// This code is contributed by amal kumar choubey
Producción:
15 18
Complejidad de tiempo: O(Q * logN)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA