Cuente distinto Bitwise OR de todos los Subarreglos

Dada una array A de enteros no negativos, donde  . La tarea es contar el número de distintos resultados posibles obtenidos al tomar el OR bit a bit de todos los elementos en todos los Subarreglos posibles.
Ejemplos: 
 

Input: A = [1, 2]
Output: 3
Explanation: The possible subarrays are [1], [2], [1, 2].
These Bitwise OR of subarrays are 1, 2, 3.
There are 3 distinct values, so the answer is 3.

Input: A = [1, 2, 4]
Output: 6
Explanation: The possible distinct values are 1, 2, 3, 4, 6, and 7.

Enfoque: 
el enfoque Naive es generar todos los subarreglos posibles y tomar OR bit a bit de todos los elementos en el subarreglo. Almacene cada resultado en un conjunto y devuelva la longitud del conjunto . 
Enfoque eficiente: 
podemos mejorar el enfoque anterior. El enfoque Naive es calcular todos los resultados posibles donde, res(i, j) = A[i] | A[yo+1] | … | A[j] . Sin embargo, podemos acelerar esto tomando nota del hecho de que res(i, j+1) = res(i, j) | A[j+1] . En el k-ésimo paso, digamos que tenemos todos los res(i, k) en algún conjunto pre . Entonces podemos encontrar el siguiente preestablecido ( para k -> k+1) usandores(yo, k+1) = res(yo, k) | A[k+1] .
Sin embargo, el número de valores únicos en este conjunto pre es como máximo 32, ya que la lista res(k, k), res(k-1, k), res(k-2, k), … es monótona y creciente , y cualquier los valores posteriores que son diferentes de los anteriores deben tener más 1 en su representación binaria, que puede tener un máximo de 32 unos .
A continuación se muestra la implementación del enfoque anterior. 
 

# Python implementation of the above approach
 
# function to return count of distinct bitwise OR
def subarrayBitwiseOR(A):
 
    # res contains distinct values
    res = set()
 
    pre = {0}
 
    for x in A:
        pre = {x | y for y in pre} | {x}
        res |= pre
 
    return len(res)
 
 
# Driver program
A = [1, 2, 4]
 
# print required answer
print(subarrayBitwiseOR(A))
 
# This code is written by
# Sanjit_Prasad

6

Complejidad temporal: O(N*log(K)), donde N es la longitud de A y K es el tamaño máximo de los elementos de A.

Implementación en C++ del enfoque anterior.

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate count of
// distinct bitwise OR of all
// subarrays.
int distintBitwiseOR(int arr[], int n)
{
    unordered_set<int> ans, prev;
 
    for (int i = 0; i < n; i++) {
        unordered_set<int> ne;
 
        for (auto x : prev)
            ne.insert(arr[i] | x);
        ne.insert(arr[i]);
 
        for (auto x : ne)
            ans.insert(x);
 
        prev = ne;
    }
 
    return ans.size();
}
 
// Driver Code
int main()
{
    int n = 3;
    int arr[] = { 1, 2, 4 };
 
    cout << distintBitwiseOR(arr, n);
 
    return 0;
}

// Java implementation of the above approach
import java.io.*;
import java.util.*;
 
class GFG
{
   
  // function to calculate count of
// distinct bitwise OR of all
// subarrays.
 static int distintBitwiseOR(int arr[], int n)
  {
    
     HashSet<Integer>ans = new HashSet<>();
        HashSet<Integer>prev = new HashSet<>();
        for(int i = 0; i < n; i++)
        {
            HashSet<Integer>ne = new HashSet<>();
            ne.add(arr[i]);
            for(int x :prev)
            {
                ne.add(arr[i]|x);
            }
            for(int x :ne)
            {
              ans.add(x);
            }
            
            prev = ne;
        }
        return ans.size();
    }
  
    // Driver code
    public static void main (String[] args) {
         int n = 3;
         int arr[] = { 1, 2, 4 };
         System.out.println(distintBitwiseOR(arr, n));
          
    }
}
 
// This code is contributed by iramkhalid24.

# Python implementation of the above approach
 
# function to calculate count of
# distinct bitwise OR of all
# subarrays.
def distintBitwiseOR(arr,n):
 
    ans,prev = set(), set()
 
    for i in range(n):
        ne = set()
 
        for x in prev:
            ne.add(arr[i] | x)
        ne.add(arr[i])
 
        for x in ne:
            ans.add(x)
 
        prev = ne
 
    return len(ans)
 
# Driver Code
n = 3
arr = [ 1, 2, 4 ]
 
print(distintBitwiseOR(arr, n))
 
# This code is written by Shinjanpatra

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // function to calculate count of
  // distinct bitwise OR of all
  // subarrays.
  static int distintBitwiseOR(int[] arr, int n)
  {
 
    HashSet<int> ans = new HashSet<int>();
    HashSet<int> prev = new HashSet<int>();
 
    for (int i = 0; i < n; i++) {
      HashSet<int> ne = new HashSet<int>();
      ne.Add(arr[i]);
      foreach(var x in prev) { ne.Add(arr[i] | x); }
 
      foreach(var x in ne) { ans.Add(x); }
 
      prev = ne;
    }
    return ans.Count;
  }
 
  // Driver code
  public static void Main(string[] args)
  {
    int n = 3;
    int[] arr = { 1, 2, 4 };
 
    // Function call
    Console.WriteLine(distintBitwiseOR(arr, n));
  }
}
 
// This code is contributed by phasing17

<script>
 
// JavaScript implementation of the above approach
 
// function to calculate count of
// distinct bitwise OR of all
// subarrays.
function distintBitwiseOR(arr,n)
{
    let ans = new Set(), prev = new Set();
 
    for (let i = 0; i < n; i++) {
        let ne = new Set();
 
        for (let x of prev)
            ne.add(arr[i] | x);
        ne.add(arr[i]);
 
        for (let x of ne)
            ans.add(x);
 
        prev = ne;
    }
 
    return ans.size;
}
 
// Driver Code
 
let n = 3;
let arr = [ 1, 2, 4 ];
 
document.write(distintBitwiseOR(arr, n));
 
// This code is written by Shinjanpatra
 
</script>

6