Dada una array arr[] y un entero K , la tarea es contar el número de sub-arrays que tienen OR bit a bit ≥ K.
Ejemplos:
Entrada: arr[] = { 1, 2, 3 } K = 3
Salida: 4
O bit a bit de subarrays:
{ 1 } = 1
{ 1, 2 } = 3
{ 1, 2, 3 } = 3
{ 2 } = 2
{ 2, 3 } = 3
{ 3 } = 3
4 sub-arrays tienen OR bit a bit ≥ KEntrada: arr[] = { 3, 4, 5 } K = 6
Salida: 2
Enfoque ingenuo: ejecute tres bucles anidados. El bucle más externo determina el inicio del subarreglo. El bucle central determina el final del subarreglo. El bucle más interno atraviesa el subarreglo cuyos límites están determinados por los bucles más externo y medio. Para cada subarreglo, calcule OR y actualice count = count + 1 si OR es mayor que K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of required sub-arrays
int countSubArrays(const int* arr, int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int bitwise_or = 0;
// Traverse sub-array [i..j]
for (int k = i; k <= j; k++) {
bitwise_or = bitwise_or | arr[k];
}
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << countSubArrays(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class solution
{
// Function to return the count of required sub-arrays
static int countSubArrays(int arr[], int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int bitwise_or = 0;
// Traverse sub-array [i..j]
for (int k = i; k <= j; k++) {
bitwise_or = bitwise_or | arr[k];
}
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 3, 4, 5 };
int n = arr.length;
int k = 6;
System.out.println(countSubArrays(arr, n, k));
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach # Function to return the count of # required sub-arrays def countSubArrays(arr, n, K) : count = 0; for i in range(n) : for j in range(i, n) : bitwise_or = 0 # Traverse sub-array [i..j] for k in range(i, j + 1) : bitwise_or = bitwise_or | arr[k] if (bitwise_or >= K) : count += 1 return count # Driver code if __name__ == "__main__" : arr = [ 3, 4, 5 ] n = len(arr) k = 6 print(countSubArrays(arr, n, k)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of
// required sub-arrays
static int countSubArrays(int []arr,
int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
int bitwise_or = 0;
// Traverse sub-array [i..j]
for (int k = i; k <= j; k++)
{
bitwise_or = bitwise_or | arr[k];
}
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
public static void Main()
{
int []arr = { 3, 4, 5 };
int n = arr.Length;
int k = 6;
Console.WriteLine(countSubArrays(arr, n, k));
}
}
// This code is contributed by
// Mohit kumar
PHP
<?php
// PHP implementation of the approach
// Function to return the count of
// required sub-arrays
function countSubArrays($arr, $n, $K)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $n; $j++)
{
$bitwise_or = 0;
// Traverse sub-array [i..j]
for ($k = $i; $k < $j + 1; $k++)
$bitwise_or = $bitwise_or | $arr[$k];
if ($bitwise_or >= $K)
$count += 1;
}
}
return $count;
}
// Driver code
$arr = array( 3, 4, 5 );
$n = count($arr);
$k = 6;
print(countSubArrays($arr, $n, $k));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of required sub-arrays
function countSubArrays(arr, n, K)
{
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
let bitwise_or = 0;
// Traverse sub-array [i..j]
for (let k = i; k <= j; k++) {
bitwise_or = bitwise_or | arr[k];
}
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
let arr = [ 3, 4, 5 ];
let n = arr.length;
let k = 6;
document.write(countSubArrays(arr, n, k));
// This code is contributed by suresh07.
</script>
Producción:
2
La complejidad temporal de la solución anterior es O(n 3 ) y el espacio auxiliar es O(1). Una solución eficiente utiliza árboles de segmentos para calcular OR bit a bit de un subarreglo en tiempo O (log n) . Por lo tanto, ahora consultamos directamente el árbol de segmentos en lugar de atravesar el subarreglo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100002
int tree[4 * N];
// Function to build the segment tree
void build(int* arr, int node, int start, int end)
{
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function to return the bitwise OR of segment [L..R]
int query(int node, int start, int end, int l, int r)
{
if (start > end || start > r || end < l) {
return 0;
}
if (start >= l && end <= r) {
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to return the count of required sub-arrays
int countSubArrays(int arr[], int n, int K)
{
// Build segment tree
build(arr, 1, 0, n - 1);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// Query segment tree for bitwise OR
// of sub-array [i..j]
int bitwise_or = query(1, 0, n - 1, i, j);
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 6;
cout << countSubArrays(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
public class Main
{
static int N = 100002;
static int tree[] = new int[4 * N];
// Function to build the segment tree
static void build(int arr[], int node,
int start, int end)
{
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function to return the bitwise OR of segment [L..R]
static int query(int node, int start,
int end, int l, int r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to return the count of required sub-arrays
static int countSubArrays(int arr[], int n, int K)
{
// Build segment tree
build(arr, 1, 0, n - 1);
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// Query segment tree for bitwise OR
// of sub-array [i..j]
int bitwise_or = query(1, 0, n - 1, i, j);
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 3, 4, 5 };
int n = arr.length;
int k = 6;
System.out.print(countSubArrays(arr, n, k));
}
}
// This code is contributed by divyesh072019
Python3
# Python implementation of the approach N = 100002 tree = [0]*(4 * N) # Function to build the segment tree def build(arr, node, start, end): if start == end: tree[node] = arr[start] return mid = (start + end) >> 1 build(arr, 2 * node, start, mid) build(arr, 2 * node + 1, mid + 1, end) tree[node] = tree[2 * node] | tree[2 * node + 1] # Function to return the bitwise OR of segment[L..R] def query(node, start, end, l, r): if start > end or start > r or end < l: return 0 if start >= l and end <= r: return tree[node] mid = (start + end) >> 1 q1 = query(2 * node, start, mid, l, r) q2 = query(2 * node + 1, mid + 1, end, l, r) return q1 or q2 # Function to return the count of required sub-arrays def countSubArrays(arr, n, K): # Build segment tree build(arr, 1, 0, n - 1) count = 0 for i in range(n): for j in range(n): # Query segment tree for bitwise OR # of sub-array[i..j] bitwise_or = query(1, 0, n - 1, i, j) if bitwise_or >= K: count += 1 return count # Driver code arr = [3, 4, 5] n = len(arr) k = 6 print(countSubArrays(arr, n, k)) # This code is contributed by ankush_953
C#
// C# implementation of the approach
using System;
class GFG {
static int N = 100002;
static int[] tree = new int[4 * N];
// Function to build the segment tree
static void build(int[] arr, int node,
int start, int end)
{
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function to return the bitwise OR of segment [L..R]
static int query(int node, int start,
int end, int l, int r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to return the count of required sub-arrays
static int countSubArrays(int[] arr, int n, int K)
{
// Build segment tree
build(arr, 1, 0, n - 1);
int count = 0;
for (int i = 0; i < n; i++)
{
for (int j = i; j < n; j++)
{
// Query segment tree for bitwise OR
// of sub-array [i..j]
int bitwise_or = query(1, 0, n - 1, i, j);
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
static void Main() {
int[] arr = { 3, 4, 5 };
int n = arr.Length;
int k = 6;
Console.WriteLine(countSubArrays(arr, n, k));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript implementation of the approach
let N = 100002;
let tree = new Array(4 * N);
// Function to build the segment tree
function build(arr, node, start, end)
{
if (start == end)
{
tree[node] = arr[start];
return;
}
let mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function to return the bitwise OR of segment [L..R]
function query(node, start, end, l, r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
let mid = (start + end) >> 1;
let q1 = query(2 * node, start, mid, l, r);
let q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to return the count of
// required sub-arrays
function countSubArrays(arr, n, K)
{
// Build segment tree
build(arr, 1, 0, n - 1);
let count = 0;
for(let i = 0; i < n; i++)
{
for(let j = i; j < n; j++)
{
// Query segment tree for bitwise OR
// of sub-array [i..j]
let bitwise_or = query(1, 0, n - 1, i, j);
if (bitwise_or >= K)
count++;
}
}
return count;
}
// Driver code
let arr = [ 3, 4, 5 ];
let n = arr.length;
let k = 6;
document.write(countSubArrays(arr, n, k));
// This code is contributed by rag2127
</script>
Producción:
2
La complejidad temporal de la solución anterior es O(n 2 log n) y el espacio auxiliar es O(n).
Otra solución eficiente utiliza la búsqueda binaria . Bitwise OR es una función que nunca disminuye con el número de entradas. Por ejemplo:
O(a, b) ≤ O(a, b, c)
O(a 1 , a 2 , a 3 , …) ≤ O(a 1 , a 2 , a 3 , …, b)
Por esta propiedad, OR(a i , …, a j ) <= OR(a i , …, a j , a j+1 ) . Por lo tanto, si OR(a i , …, a j ) es mayor que K entonces OR(a i , …, a j , a j+1 ) también será mayor que K. Por lo tanto, una vez que encontramos un subarreglo [i. .j] cuyo OR es mayor que K, no necesitamos verificar los subarreglos [i..j+1], [i..j+2], .. y así sucesivamente, porque su OR también será mayor que K. Podemos sumar el recuento de los subarreglos restantes a la suma actual. El primer subarreglo desde un punto de partida particular cuyo OR es mayor que K se encuentra mediante la búsqueda binaria.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to implement the above approach
#include <bits/stdc++.h>
#define N 100002
using namespace std;
int tree[4 * N];
// Function which builds the segment tree
void build(int* arr, int node, int start, int end)
{
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function that returns bitwise OR of segment [L..R]
int query(int node, int start, int end, int l, int r)
{
if (start > end || start > r || end < l) {
return 0;
}
if (start >= l && end <= r) {
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to count requisite number of subarrays
int countSubArrays(const int* arr, int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++) {
// Check for subarrays starting with index i
int low = i, high = n - 1, index = INT_MAX;
while (low <= high) {
int mid = (low + high) >> 1;
// If OR of subarray [i..mid] >= K,
// then all subsequent subarrays will have OR >= K
// therefore reduce high to mid - 1
// to find the minimal length subarray
// [i..mid] having OR >= K
if (query(1, 0, n - 1, i, mid) >= K) {
index = min(index, mid);
high = mid - 1;
}
else {
low = mid + 1;
}
}
// Increase count with number of subarrays
// having OR >= K and starting with index i
if (index != INT_MAX) {
count += n - index;
}
}
return count;
}
// Driver code
int main()
{
int arr[] = { 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
// Build segment tree.
build(arr, 1, 0, n - 1);
int k = 6;
cout << countSubArrays(arr, n, k);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
static int N = 100002;
static int tree[] = new int[4 * N];
// Function which builds the segment tree
static void build(int[] arr, int node,
int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function that returns bitwise
// OR of segment [L..R]
static int query(int node, int start,
int end, int l, int r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to count requisite number of subarrays
static int countSubArrays(int[] arr,
int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++)
{
// Check for subarrays starting with index i
int low = i, high = n - 1, index = Integer.MAX_VALUE;
while (low <= high)
{
int mid = (low + high) >> 1;
// If OR of subarray [i..mid] >= K,
// then all subsequent subarrays will
// have OR >= K therefore reduce
// high to mid - 1 to find the
// minimal length subarray
// [i..mid] having OR >= K
if (query(1, 0, n - 1, i, mid) >= K)
{
index = Math.min(index, mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
// Increase count with number of subarrays
// having OR >= K and starting with index i
if (index != Integer.MAX_VALUE)
{
count += n - index;
}
}
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {3, 4, 5};
int n = arr.length;
// Build segment tree.
build(arr, 1, 0, n - 1);
int k = 6;
System.out.println(countSubArrays(arr, n, k));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to implement the above approach N = 100002 tree = [0 for i in range(4 * N)]; # Function which builds the segment tree def build(arr, node, start, end): if (start == end): tree[node] = arr[start]; return; mid = (start + end) >> 1; build(arr, 2 * node, start, mid); build(arr, 2 * node + 1, mid + 1, end); tree[node] = tree[2 * node] | tree[2 * node + 1]; # Function that returns bitwise OR of segment [L..R] def query(node, start, end, l, r): if (start > end or start > r or end < l): return 0; if (start >= l and end <= r): return tree[node]; mid = (start + end) >> 1; q1 = query(2 * node, start, mid, l, r); q2 = query(2 * node + 1, mid + 1, end, l, r); return q1 | q2; # Function to count requisite number of subarrays def countSubArrays(arr, n, K): count = 0; for i in range(n): # Check for subarrays starting with index i low = i high = n - 1 index = 1000000000 while (low <= high): mid = (low + high) >> 1; # If OR of subarray [i..mid] >= K, # then all subsequent subarrays will have OR >= K # therefore reduce high to mid - 1 # to find the minimal length subarray # [i..mid] having OR >= K if (query(1, 0, n - 1, i, mid) >= K): index = min(index, mid); high = mid - 1; else : low = mid + 1; # Increase count with number of subarrays # having OR >= K and starting with index i if (index != 1000000000): count += n - index; return count; # Driver code if __name__=='__main__': arr = [ 3, 4, 5 ] n = len(arr) # Build segment tree. build(arr, 1, 0, n - 1); k = 6; print(countSubArrays(arr, n, k)) # This code is contributed by rutvik_56.
C#
// C# implementation of the above approach
using System;
class GFG
{
static int N = 100002;
static int []tree = new int[4 * N];
// Function which builds the segment tree
static void build(int[] arr, int node,
int start, int end)
{
if (start == end)
{
tree[node] = arr[start];
return;
}
int mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function that returns bitwise
// OR of segment [L..R]
static int query(int node, int start,
int end, int l, int r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
int mid = (start + end) >> 1;
int q1 = query(2 * node, start, mid, l, r);
int q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to count requisite number of subarrays
static int countSubArrays(int[] arr,
int n, int K)
{
int count = 0;
for (int i = 0; i < n; i++)
{
// Check for subarrays starting with index i
int low = i, high = n - 1, index = int.MaxValue;
while (low <= high)
{
int mid = (low + high) >> 1;
// If OR of subarray [i..mid] >= K,
// then all subsequent subarrays will
// have OR >= K therefore reduce
// high to mid - 1 to find the
// minimal length subarray
// [i..mid] having OR >= K
if (query(1, 0, n - 1, i, mid) >= K)
{
index = Math.Min(index, mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
// Increase count with number of subarrays
// having OR >= K and starting with index i
if (index != int.MaxValue)
{
count += n - index;
}
}
return count;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {3, 4, 5};
int n = arr.Length;
// Build segment tree.
build(arr, 1, 0, n - 1);
int k = 6;
Console.WriteLine(countSubArrays(arr, n, k));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation of the above approach
let N = 100002;
let tree=new Array(4*N);
// Function which builds the segment tree
function build(arr,node,start,end)
{
if (start == end)
{
tree[node] = arr[start];
return;
}
let mid = (start + end) >> 1;
build(arr, 2 * node, start, mid);
build(arr, 2 * node + 1, mid + 1, end);
tree[node] = tree[2 * node] | tree[2 * node + 1];
}
// Function that returns bitwise
// OR of segment [L..R]
function query(node,start,end,l,r)
{
if (start > end || start > r || end < l)
{
return 0;
}
if (start >= l && end <= r)
{
return tree[node];
}
let mid = (start + end) >> 1;
let q1 = query(2 * node, start, mid, l, r);
let q2 = query(2 * node + 1, mid + 1, end, l, r);
return q1 | q2;
}
// Function to count requisite number of subarrays
function countSubArrays(arr,n,K)
{
let count = 0;
for (let i = 0; i < n; i++)
{
// Check for subarrays starting with index i
let low = i, high = n - 1, index = Number.MAX_VALUE;
while (low <= high)
{
let mid = (low + high) >> 1;
// If OR of subarray [i..mid] >= K,
// then all subsequent subarrays will
// have OR >= K therefore reduce
// high to mid - 1 to find the
// minimal length subarray
// [i..mid] having OR >= K
if (query(1, 0, n - 1, i, mid) >= K)
{
index = Math.min(index, mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
// Increase count with number of subarrays
// having OR >= K and starting with index i
if (index != Number.MAX_VALUE)
{
count += n - index;
}
}
return count;
}
// Driver code
let arr=[3, 4, 5];
let n = arr.length;
// Build segment tree.
build(arr, 1, 0, n - 1);
let k = 6;
document.write(countSubArrays(arr, n, k));
// This code is contributed by patel2127
</script>
Producción:
2
La complejidad temporal de la solución anterior es O(n log 2 n) .
Espacio Auxiliar : O(n).
Publicación traducida automáticamente
Artículo escrito por rohan23chhabra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA