Anzahl der Subarrays hat bitweises OR >= K
Bei einem gegebenen Array arr[] und einer Ganzzahl K besteht die Aufgabe darin, die Anzahl der Teilarrays mit bitweisem OR ≥ K zu zählen .
Beispiele:
Input: arr[] = { 1, 2, 3 } K = 3
Output: 4
Bitweises OR von Subarrays:
{ 1 } = 1
{ 1, 2 } = 3
{ 1, 2, 3 } = 3
{ 2 } = 2
{ 2, 3 } = 3
{ 3 } = 3
4 Subarrays haben bitweises OR ≥ KEingabe: arr[] = { 3, 4, 5 } K = 6
Ausgabe: 2
Naiver Ansatz: Führen Sie drei verschachtelte Schleifen aus. Die äußerste Schleife bestimmt den Beginn des Sub-Arrays. Die mittlere Schleife bestimmt das Ende des Teilarrays. Die innerste Schleife durchquert das Teilarray, dessen Grenzen durch die äußerste und die mittlere Schleife bestimmt werden. Berechnen Sie für jedes Subarray OR und aktualisieren Sie count = count + 1 , wenn OR größer als K ist .
Unten ist die Implementierung des obigen Ansatzes:
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>
Ausgabe:
2
Die Zeitkomplexität der obigen Lösung ist O(n 3 ) und der Hilfsraum ist O(1). Eine effiziente Lösung verwendet Segmentbäume , um ein bitweises ODER eines Teilarrays in O(log n) -Zeit zu berechnen . Daher fragen wir jetzt direkt den Segmentbaum ab, anstatt das Teilarray zu durchlaufen.
Unten ist die Implementierung des obigen Ansatzes:
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>
Ausgabe:
2
Die Zeitkomplexität der obigen Lösung ist O(n 2 log n) und der Hilfsraum ist O( n).
Eine weitere effiziente Lösung verwendet die binäre Suche . Bitwise OR ist eine Funktion, die niemals mit der Anzahl der Eingänge abnimmt. Beispielsweise:
OR(a, b) ≤ OR(a, b, c)
OR(a 1 , a 2 , a 3 , …) ≤ OR(a 1 , a 2 , a 3 , …, b)
Durch diese Eigenschaft ist OR(a i , …, a j ) <= OR(a i , …, a j , a j+1 ) . Wenn also OR(a i , …, a j ) größer als K ist, dann wird OR(a i , …, a j , a j+1 ) auch größer als K sein. Sobald wir also ein Subarray [i. .j] , deren OR größer als K ist, müssen wir Subarrays nicht prüfen [i..j+1], [i..j+2], .. und so weiter nicht prüfen, weil ihr OR auch größer als K sein wird. Wir können die Anzahl der verbleibenden Subarrays zur aktuellen Summe addieren. Das erste Subarray von einem bestimmten Startpunkt, dessen OR größer als K ist, wird unter Verwendung einer binären Suche gefunden.
Unten ist die Umsetzung der obigen Idee:
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>
Ausgabe:
2
Die Zeitkomplexität der obigen Lösung ist O(n log 2 n) .
Hilfsraum : O(n).
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .