Recuento de elementos que son potencia de 2 en un subarreglo de rango dado para consultas Q

Dada una array arr[] que consta de N números positivos y Q consultas de la forma [L, R] , la tarea es encontrar la cantidad de elementos que son una potencia de dos en una subarreferencia [L, R] para cada consulta. 

Ejemplos: 

Entrada: arr[] = { 3, 8, 5, 2, 5, 10 }, Q = {{0, 4}, {3, 5}} 
Salida: 
2 
1 
Explicación: 
Para la Consulta 1, el subarreglo [3, 8, 5, 2, 5] tiene 2 elementos que son una potencia de dos, 8 y 2. 
Para la Consulta 2, el subarreglo {2, 5, 10} tiene 1 elemento que son una potencia de dos, 2.
Entrada: arr [] = { 1, 2, 3, 4, 5, 6 }, Q = {{0, 4}, {1, 5}} 
Salida: 
3 
2  

Enfoque ingenuo: para resolver el problema mencionado anteriormente, el enfoque ingenuo es que para todas las consultas Q, podemos iterar a través de cada L y R en la array y encontrar la cantidad de elementos que son una potencia de dos en un subarreglo [L, R ]. 
Complejidad de tiempo: O(N * Q)

Enfoque eficiente: 
para optimizar el método anterior, la idea aquí es usar una array de suma de prefijos .  

• Inicialmente, la array de suma de prefijos contiene 0 para todos los índices.
• Itere a través de la array dada y establezca la array de prefijos para este índice en 1 si el elemento de la array actual es una potencia de dos; de lo contrario, déjelo en 0.
• Ahora, obtenga la suma del prefijo agregando el valor de la array de prefijos del índice anterior para calcular la suma del prefijo del índice actual. el prefijo [i] almacenará el número de elementos que son una potencia de dos de 1 a i.
• Una vez que tenemos la array de prefijos, solo tenemos que devolver prefijo[r] – prefijo[l-1] para cada consulta.

A continuación se muestra la implementación del enfoque anterior, 

// C++ implementation to find
// elements that are a power of two
 
#include <bits/stdc++.h>
using namespace std;
const int MAX = 10000;
 
// prefix[i] is going to store the
// number of elements which are a
// power of two till i (including i).
int prefix[MAX + 1];
 
bool isPowerOfTwo(int x)
{
    if (x && (!(x & (x - 1))))
        return true;
    return false;
}
 
// Function to find the maximum range
// whose sum is divisible by M.
void computePrefix(int n, int a[])
{
 
    // Calculate the prefix sum
    if (isPowerOfTwo(a[0]))
        prefix[0] = 1;
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1];
 
        if (isPowerOfTwo(a[i]))
            prefix[i]++;
    }
}
 
// Function to return the number of elements
// which are a power of two in a subarray
int query(int L, int R)
{
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
int main()
{
    int A[] = { 3, 8, 5, 2, 5, 10 };
    int N = sizeof(A) / sizeof(A[0]);
    int Q = 2;
 
    computePrefix(N, A);
    cout << query(0, 4) << "\n";
    cout << query(3, 5) << "\n";
 
    return 0;
}

// Java implementation to find
// elements that are a power of two
import java.util.*;
class GFG{
     
static final int MAX = 10000;
 
// prefix[i] is going to store the
// number of elements which are a
// power of two till i (including i).
static int[] prefix = new int[MAX + 1];
 
static boolean isPowerOfTwo(int x)
{
    if (x != 0 && ((x & (x - 1)) == 0))
        return true;
    return false;
}
 
// Function to find the maximum range
// whose sum is divisible by M.
static void computePrefix(int n, int a[])
{
 
    // Calculate the prefix sum
    if (isPowerOfTwo(a[0]))
        prefix[0] = 1;
    for (int i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1];
 
        if (isPowerOfTwo(a[i]))
            prefix[i]++;
    }
}
 
// Function to return the number of elements
// which are a power of two in a subarray
static int query(int L, int R)
{
    if (L == 0)
        return prefix[R];
 
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
public static void main(String[] args)
{
    int A[] = { 3, 8, 5, 2, 5, 10 };
    int N = A.length;
    int Q = 2;
 
    computePrefix(N, A);
    System.out.println(query(0, 4));
    System.out.println(query(3, 5));
}
}
 
// This code is contributed by offbeat

# Python3 implementation to find
# elements that are a power of two
MAX = 10000
 
# prefix[i] is going to store the
# number of elements which are a
# power of two till i (including i).
prefix = [0] * (MAX + 1)
 
def isPowerOfTwo(x):
     
    if (x and (not (x & (x - 1)))):
        return True
    return False
 
# Function to find the maximum range
# whose sum is divisible by M.
def computePrefix(n, a):
 
    # Calculate the prefix sum
    if (isPowerOfTwo(a[0])):
        prefix[0] = 1
         
    for i in range(1, n):
        prefix[i] = prefix[i - 1]
 
        if (isPowerOfTwo(a[i])):
            prefix[i] += 1
 
# Function to return the number of elements
# which are a power of two in a subarray
def query(L, R):
     
    return prefix[R] - prefix[L - 1]
 
# Driver code
if __name__ == "__main__":
     
    A = [ 3, 8, 5, 2, 5, 10 ]
    N = len(A)
    Q = 2
 
    computePrefix(N, A)
    print(query(0, 4))
    print(query(3, 5))
 
# This code is contributed by chitranayal

// C# implementation to find
// elements that are a power of two
using System;
class GFG{
     
static int MAX = 10000;
 
// prefix[i] is going to store the
// number of elements which are a
// power of two till i (including i).
static int[] prefix = new int[MAX + 1];
 
static bool isPowerOfTwo(int x)
{
    if (x != 0 && ((x & (x - 1)) == 0))
        return true;
    return false;
}
 
// Function to find the maximum range
// whose sum is divisible by M.
static void computePrefix(int n, int []a)
{
 
    // Calculate the prefix sum
    if (isPowerOfTwo(a[0]))
        prefix[0] = 1;
    for (int i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1];
 
        if (isPowerOfTwo(a[i]))
            prefix[i]++;
    }
}
 
// Function to return the number of elements
// which are a power of two in a subarray
static int query(int L, int R)
{
    if (L == 0)
        return prefix[R];
 
    return prefix[R] - prefix[L - 1];
}
 
// Driver code
public static void Main()
{
    int []A = { 3, 8, 5, 2, 5, 10 };
    int N = A.Length;
 
    computePrefix(N, A);
    Console.WriteLine(query(0, 4));
    Console.WriteLine(query(3, 5));
}
}
 
// This code is contributed by Code_Mech

<script>
 
// Javascript implementation to find
// elements that are a power of two
 
let MAX = 10000;
   
// prefix[i] is going to store the
// number of elements which are a
// power of two till i (including i).
let prefix = Array.from({length: MAX + 1}, (_, i) => 0);
   
function isPowerOfTwo(x)
{
    if (x != 0 && ((x & (x - 1)) == 0))
        return true;
    return false;
}
   
// Function to find the maximum range
// whose sum is divisible by M.
function computePrefix(n, a)
{
   
    // Calculate the prefix sum
    if (isPowerOfTwo(a[0]))
        prefix[0] = 1;
    for (let i = 1; i < n; i++)
    {
        prefix[i] = prefix[i - 1];
   
        if (isPowerOfTwo(a[i]))
            prefix[i]++;
    }
}
   
// Function to return the number of elements
// which are a power of two in a subarray
function query(L, R)
{
    if (L == 0)
        return prefix[R];
   
    return prefix[R] - prefix[L - 1];
}
 
// Driver Code
     
    let A = [ 3, 8, 5, 2, 5, 10 ];
    let N = A.length;
   
    computePrefix(N, A);
    document.write(query(0, 4) + "<br/>");
    document.write(query(3, 5));
     
</script>

2
1

Complejidad del tiempo: O(max(Q, N))