Count of elements which are power of 2 in a given range subarray for Q queries
Given an array arr[] consisting of N positive numbers and Q queries of the form [L, R], the task is to find the number of elements which are a power of two in a subarray [L, R] for each query.
Examples:
Input: arr[] = { 3, 8, 5, 2, 5, 10 }, Q = {{0, 4}, {3, 5}}
Output:
2
1
Explanation:
For Query 1, the subarray [3, 8, 5, 2, 5] has 2 elements which are a power of two, 8 and 2.
For Query 2, the subarray {2, 5, 10} has 1 element which are a power of two, 2.
Input: arr[] = { 1, 2, 3, 4, 5, 6 }, Q = {{0, 4}, {1, 5}}
Output:
3
2
Naive Approach: To solve the problem mentioned above the naive approach is that for all the Q queries, we can iterate through each L and R in the array and find the number of elements which are a power of two in a subarray [L, R].
Time Complexity: O(N * Q)
Efficient Approach:
To optimize the above method the idea here is to use a prefix sum array.
- Initially, the prefix sum array contains 0 for all indices.
- Iterate through the given array and set the prefix array for this index to 1 if the current array element is a power of two else leave it 0.
- Now, obtain the prefix sum by adding the previous index prefix array value to compute the current index’s prefix sum. the prefix[i] will store the number of elements which are a power of two from 1 to i.
- Once we have prefix array, We just need to return prefix[r] – prefix[l-1] for each query.
Below is the implementation of the above approach,
C++
// 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
// 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
# 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#
// 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 |
Javascript
<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
Time Complexity: O(max(Q, N))
Contact Us