Dada una array de N enteros positivos (32 bits), la tarea es responder Q consultas de la siguiente forma:
Query(L, R, K): Print the number of elements of the array in the range L to R, which have their Kth bit as set
Nota : considere LSB indexado en 1 .
Ejemplos:
Entrada : arr[] = { 8, 9, 1, 3 }
Consulta 1: L = 1, R = 3, K = 4
Consulta 2: L = 2, R = 4, K = 1
Salida :
2
3
Explicación :
Para la primera consulta, el rango (1, 3) representa elementos, {8, 9, 1}. Entre estos elementos sólo el 8 y el 9 tienen su 4º bit activado. Por lo tanto, la respuesta a esta consulta es 2 .
Para la segunda consulta, el rango (2, 4) representa elementos, {9, 1, 3}. Todos estos elementos tienen su 1er bit establecido. Por lo tanto, la respuesta para esta consulta es 3 .
Requisitos previos : Manipulación de bits | Arrays de suma de prefijos
Método 1 (Fuerza bruta) : para cada consulta, recorra la array de L a R, y en cada índice verifique si el elemento de la array en ese índice tiene su K -ésimo bit establecido. Si incrementa la variable contador.
A continuación se muestra la implementación del enfoque anterior.
C++
/* C++ Program to find the number of elements in a range L to R having the Kth bit as set */ #include <bits/stdc++.h> using namespace std; // Maximum bits required in binary representation // of an array element #define MAX_BITS 32 /* Returns true if n has its kth bit as set, else returns false */ bool isKthBitSet(int n, int k) { if (n & (1 << (k - 1))) return true; return false; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ int answerQuery(int L, int R, int K, int arr[]) { // counter stores the number of element in // the range with the kth bit set int counter = 0; for (int i = L; i <= R; i++) { if (isKthBitSet(arr[i], K)) { counter++; } } return counter; } // Print the answer for all queries void answerQueries(int queries[][3], int Q, int arr[], int N) { int query_L, query_R, query_K; for (int i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; cout << "Result for Query " << i + 1 << " = " << answerQuery(query_L, query_R, query_K, arr) << endl; } } // Driver Code int main() { int arr[] = { 8, 9, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int queries[][3] = { { 1, 3, 4 }, { 2, 4, 1 } }; int Q = sizeof(queries) / sizeof(queries[0]); answerQueries(queries, Q, arr, N); return 0; }
Java
// Java Program to find the // number of elements in a // range L to R having the // Kth bit as set import java.util.*; import java.lang.*; import java.io.*; // Maximum bits required // in binary representation // of an array element class GFG { static final int MAX_BITS = 32; /* Returns true if n has its kth bit as set, else returns false */ static boolean isKthBitSet(int n, int k) { if ((n & (1 << (k - 1))) != 0) return true; return false; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ static int answerQuery(int L, int R, int K, int arr[]) { // counter stores the number // of element in the range // with the kth bit set int counter = 0; for (int i = L; i <= R; i++) { if (isKthBitSet(arr[i], K)) { counter++; } } return counter; } // Print the answer // for all queries static void answerQueries(int queries[][], int Q, int arr[], int N) { int query_L, query_R, query_K; for (int i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; System.out.println("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, arr)); } } // Driver Code public static void main(String args[]) { int arr[] = { 8, 9, 1, 3 }; int N = arr.length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int queries[][] = { { 1, 3, 4 }, { 2, 4, 1 } }; int Q = queries.length; answerQueries(queries, Q, arr, N); } } // This code is contributed // by Subhadeep
Python3
# Python3 Program to find the number of elements # in a range L to R having the Kth bit as set # Maximum bits required in binary representation # of an array element MAX_BITS = 32 # Returns true if n has its kth bit as set, # else returns false def isKthBitSet(n, k): if (n & (1 << (k - 1))): return True return False # Returns the answer for each query with range L # to R querying for the number of elements with # the Kth bit set in the range def answerQuery(L, R, K, arr): # counter stores the number of element # in the range with the kth bit set counter = 0 for i in range(L, R + 1): if (isKthBitSet(arr[i], K)): counter += 1 return counter # Print the answer for all queries def answerQueries(queries, Q, arr, N): for i in range(Q): query_L = queries[i][0] - 1 query_R = queries[i][1] - 1 query_K = queries[i][2] print("Result for Query", i + 1, "=", answerQuery(query_L, query_R, query_K, arr)) # Driver Code if __name__ == "__main__": arr = [ 8, 9, 1, 3 ] N = len(arr) # queries[][] denotes the array of queries # where each query has three integers # query[i][0] -> Value of L for ith query # query[i][0] -> Value of R for ith query # query[i][0] -> Value of K for ith query queries = [[ 1, 3, 4 ], [ 2, 4, 1 ]] Q = len(queries) answerQueries(queries, Q, arr, N) # This code is contributed by ita_c
C#
// C# Program to find the number of // elements in a range L to R having // the Kth bit as set using System; // Maximum bits required // in binary representation // of an array element class GFG { static readonly int MAX_BITS = 32; /* Returns true if n has its kth bit as set, else returns false */ static bool isKthBitSet(int n, int k) { if ((n & (1 << (k - 1))) != 0) return true; return false; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ static int answerQuery(int L, int R, int K, int []arr) { // counter stores the number // of element in the range // with the kth bit set int counter = 0; for (int i = L; i <= R; i++) { if (isKthBitSet(arr[i], K)) { counter++; } } return counter; } // Print the answer for all queries static void answerQueries(int [,]queries, int Q, int []arr, int N) { int query_L, query_R, query_K; for (int i = 0; i < Q; i++) { query_L = queries[i,0] - 1; query_R = queries[i,1] - 1; query_K = queries[i,2]; Console.WriteLine("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, arr)); } } // Driver Code public static void Main() { int []arr = { 8, 9, 1, 3 }; int N = arr.Length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int [,]queries = { { 1, 3, 4 }, { 2, 4, 1 } }; int Q = queries.GetLength(0); answerQueries(queries, Q, arr, N); } } // This code is contributed // by 29AjayKumar
Javascript
<script> // Javascript Program to find the // number of elements in a // range L to R having the // Kth bit as set // Maximum bits required // in binary representation // of an array element let MAX_BITS = 32; /* Returns true if n has its kth bit as set, else returns false */ function isKthBitSet(n,k) { if ((n & (1 << (k - 1))) != 0) return true; return false; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ function answerQuery(L,R,K,arr) { // counter stores the number // of element in the range // with the kth bit set let counter = 0; for (let i = L; i <= R; i++) { if (isKthBitSet(arr[i], K)) { counter++; } } return counter; } // Print the answer // for all queries function answerQueries(queries,Q,arr,N) { let query_L, query_R, query_K; for (let i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; document.write("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, arr)+"<br>"); } } // Driver Code let arr=[8, 9, 1, 3]; let N = arr.length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ let queries = [ [ 1, 3, 4 ], [ 2, 4, 1 ] ]; let Q = queries.length; answerQueries(queries, Q, arr, N); // This code is contributed by unknown2108 </script>
Result for Query 1 = 2 Result for Query 2 = 3
Complejidad de tiempo : O(N) para cada consulta.
Método 2 (eficiente) : suponiendo que cada número entero en la array tiene un máximo de 32 bits en su representación binaria. Se puede construir una array de suma de prefijos 2D para resolver el problema. Aquí, la segunda dimensión de la array de prefijos tiene un tamaño igual al número máximo de bits necesarios para representar un número entero de la array en binario.
Deje que la array de suma de prefijos sea P[][] . Ahora, P[i][j] denota el número de Elementos de 0 a i , que tienen su j -ésimo bit establecido. Esta array de suma de prefijos se construye antes de responder a las consultas. Si se encuentra una consulta de L a R, la consulta de elementos en este rango que tengan su Kth bit como se establece, entonces la respuesta para esa consulta es P[R][K] – P[L – 1][K] .
A continuación se muestra la implementación del enfoque anterior.
C++
/* C++ Program to find the number of elements in a range L to R having the Kth bit as set */ #include <bits/stdc++.h> using namespace std; // Maximum bits required in binary representation // of an array element #define MAX_BITS 32 /* Returns true if n has its kth bit as set, else returns false */ bool isKthBitSet(int n, int k) { if (n & (1 << (k - 1))) return true; return false; } // Return pointer to the prefix sum array int** buildPrefixArray(int N, int arr[]) { // Build a prefix sum array P[][] // where P[i][j] represents the number of // elements from 0 to i having the jth bit as set int** P = new int*[N + 1]; for (int i = 0; i <= N; ++i) { P[i] = new int[MAX_BITS + 1]; } for (int i = 0; i <= MAX_BITS; i++) { P[0][i] = 0; } for (int i = 0; i < N; i++) { for (int j = 1; j <= MAX_BITS; j++) { // prefix sum from 0 to i for each bit // position jhas the value of sum from 0 // to i-1 for each j if (i) P[i][j] = P[i - 1][j]; // if jth bit set then increment P[i][j] by 1 bool isJthBitSet = isKthBitSet(arr[i], j); if (isJthBitSet) { P[i][j]++; } } } return P; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ int answerQuery(int L, int R, int K, int** P) { /* Number of elements in range L to R with Kth bit set = (Number of elements from 0 to R with kth bit set) - (Number of elements from 0 to L-1 with kth bit set) */ if (L) return P[R][K] - P[L - 1][K]; else return P[R][K]; } // Print the answer for all queries void answerQueries(int queries[][3], int Q, int arr[], int N) { // Build Prefix Array to answer queries efficiently int** P = buildPrefixArray(N, arr); int query_L, query_R, query_K; for (int i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; cout << "Result for Query " << i + 1 << " = " << answerQuery(query_L, query_R, query_K, P) << endl; } } // Driver Code int main() { int arr[] = { 8, 9, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int queries[][3] = { { 1, 3, 4 }, { 2, 4, 1 } }; int Q = sizeof(queries) / sizeof(queries[0]); answerQueries(queries, Q, arr, N); return 0; }
Java
/* Java Program to find the number of elements in a range L to R having the Kth bit as set */ import java.io.*; class GFG { // Maximum bits required in binary representation // of an array element static int MAX_BITS = 32; /* Returns true if n has its kth bit as set, else returns false */ static boolean isKthBitSet(int n, int k) { if((n & (1 << (k - 1))) != 0) { return true; } return false; } // Return pointer to the prefix sum array static int[][] buildPrefixArray(int N, int[] arr) { // Build a prefix sum array P[][] // where P[i][j] represents the number of // elements from 0 to i having the jth bit as set int[][] P = new int[N + 1][MAX_BITS + 1]; for(int i = 0; i <= MAX_BITS; i++) { P[0][i] = 0; } for(int i = 0; i < N; i++) { for(int j = 1; j <= MAX_BITS; j++) { // prefix sum from 0 to i for each bit // position jhas the value of sum from 0 // to i-1 for each j if(i != 0) { P[i][j] = P[i - 1][j]; } // if jth bit set then increment P[i][j] by 1 boolean isJthBitSet = isKthBitSet(arr[i], j); if(isJthBitSet) { P[i][j]++; } } } return P; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ static int answerQuery(int L, int R, int K, int[][] P) { /* Number of elements in range L to R with Kth bit set = (Number of elements from 0 to R with kth bit set) - (Number of elements from 0 to L-1 with kth bit set) */ if(L != 0) { return P[R][K] - P[L - 1][K]; } else { return P[R][K]; } } // Print the answer for all queries static void answerQueries(int[][] queries,int Q, int[] arr, int N) { // Build Prefix Array to answer queries efficiently int[][] P = buildPrefixArray(N, arr); int query_L, query_R, query_K; for(int i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; System.out.println("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, P)); } } // Driver Code public static void main (String[] args) { int[] arr = {8, 9, 1, 3}; int N = arr.length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int[][] queries = {{1, 3, 4},{2, 4, 1}}; int Q = queries.length; answerQueries(queries, Q, arr, N); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find the number # of elements in a range L to R having # the Kth bit as set # Maximum bits required in binary # representation of an array element MAX_BITS = 32 # Returns true if n has its kth # bit as set,else returns false def isKthBitSet(n, k): if (n & (1 << (k - 1))): return True return False # Return pointer to the prefix sum array def buildPrefixArray(N, arr): # Build a prefix sum array P[][] # where P[i][j] represents the # number of elements from 0 to # i having the jth bit as set P = [[0 for i in range(MAX_BITS + 1)] for i in range(N + 1)] for i in range(N): for j in range(1, MAX_BITS + 1): # prefix sum from 0 to i for each bit # position jhas the value of sum from 0 # to i-1 for each j if (i): P[i][j] = P[i - 1][j] # If jth bit set then increment # P[i][j] by 1 isJthBitSet = isKthBitSet(arr[i], j) if (isJthBitSet): P[i][j] += 1 return P # Returns the answer for each query # with range L to R querying for the # number of elements with the Kth bit # set in the range def answerQuery(L, R, K, P): # Number of elements in range L to # R with Kth bit set = (Number of # elements from 0 to R with kth # bit set) - (Number of elements # from 0 to L-1 with kth bit set) if (L): return P[R][K] - P[L - 1][K] else: return P[R][K] # Print the answer for all queries def answerQueries(queries, Q, arr, N): # Build Prefix Array to answer # queries efficiently P = buildPrefixArray(N, arr) for i in range(Q): query_L = queries[i][0] - 1 query_R = queries[i][1] - 1 query_K = queries[i][2] print("Result for Query ", i + 1, " = ", answerQuery(query_L, query_R, query_K, P)) # Driver Code if __name__ == '__main__': arr = [ 8, 9, 1, 3 ] N = len(arr) # queries[]denotes the array of queries # where each query has three integers # query[i][0] -> Value of L for ith query # query[i][0] -> Value of R for ith query # query[i][0] -> Value of K for ith query queries = [ [ 1, 3, 4 ], [ 2, 4, 1 ] ] Q = len(queries) answerQueries(queries, Q, arr, N) # This code is contributed by mohit kumar 29
C#
// C# program to find the number of elements // in a range L to R having the Kth bit as set using System; class GFG{ // Maximum bits required in binary representation // of an array element static int MAX_BITS = 32; // Returns true if n has its kth bit as set, // else returns false static bool isKthBitSet(int n, int k) { if ((n & (1 << (k - 1))) != 0) { return true; } return false; } // Return pointer to the prefix sum array static int[,] buildPrefixArray(int N, int[] arr) { // Build a prefix sum array P[][] // where P[i][j] represents the // number of elements from 0 to i // having the jth bit as set int[,] P = new int[N + 1, MAX_BITS + 1]; for(int i = 0; i <= MAX_BITS; i++) { P[0, i] = 0; } for(int i = 0; i < N; i++) { for(int j = 1; j <= MAX_BITS; j++) { // prefix sum from 0 to i for each bit // position jhas the value of sum from 0 // to i-1 for each j if (i != 0) { P[i, j] = P[i - 1, j]; } // If jth bit set then increment P[i][j] by 1 bool isJthBitSet = isKthBitSet(arr[i], j); if (isJthBitSet) { P[i, j]++; } } } return P; } // Returns the answer for each query with range // L to R querying for the number of elements with // the Kth bit set in the range static int answerQuery(int L, int R, int K, int[,] P) { // Number of elements in range L to R with Kth // bit set = (Number of elements from 0 to R with // kth bit set) - (Number of elements from 0 to L-1 // with kth bit set) if (L != 0) { return P[R, K] - P[L - 1, K]; } else { return P[R, K]; } } // Print the answer for all queries static void answerQueries(int[,] queries, int Q, int[] arr, int N) { // Build Prefix Array to answer queries efficiently int[,] P = buildPrefixArray(N, arr); int query_L, query_R, query_K; for(int i = 0; i < Q; i++) { query_L = queries[i, 0] - 1; query_R = queries[i, 1] - 1; query_K = queries[i, 2]; Console.WriteLine("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, P)); } } // Driver Code static public void Main() { int[] arr = { 8, 9, 1, 3 }; int N = arr.Length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ int[,] queries = { { 1, 3, 4 }, { 2, 4, 1 } }; int Q = queries.GetLength(0); answerQueries(queries, Q, arr, N); } } // This code is contributed by rag2127
Javascript
<script> /* Javascript Program to find the number of elements in a range L to R having the Kth bit as set */ // Maximum bits required in binary representation // of an array element let MAX_BITS = 32; /* Returns true if n has its kth bit as set, else returns false */ function isKthBitSet(n,k) { if((n & (1 << (k - 1))) != 0) { return true; } return false; } // Return pointer to the prefix sum array function buildPrefixArray(N,arr) { // Build a prefix sum array P[][] // where P[i][j] represents the number of // elements from 0 to i having the jth bit as set let P = new Array(N + 1); for(let i=0;i<P.length;i++) { P[i]=new Array(MAX_BITS+1); } for(let i = 0; i <= MAX_BITS; i++) { P[0][i] = 0; } for(let i = 0; i < N; i++) { for(let j = 1; j <= MAX_BITS; j++) { // prefix sum from 0 to i for each bit // position jhas the value of sum from 0 // to i-1 for each j if(i != 0) { P[i][j] = P[i - 1][j]; } // if jth bit set then increment P[i][j] by 1 let isJthBitSet = isKthBitSet(arr[i], j); if(isJthBitSet) { P[i][j]++; } } } return P; } /* Returns the answer for each query with range L to R querying for the number of elements with the Kth bit set in the range */ function answerQuery(L,R,K,P) { /* Number of elements in range L to R with Kth bit set = (Number of elements from 0 to R with kth bit set) - (Number of elements from 0 to L-1 with kth bit set) */ if(L != 0) { return P[R][K] - P[L - 1][K]; } else { return P[R][K]; } } // Print the answer for all queries function answerQueries(queries,Q,arr,N) { // Build Prefix Array to answer queries efficiently let P = buildPrefixArray(N, arr); let query_L, query_R, query_K; for(let i = 0; i < Q; i++) { query_L = queries[i][0] - 1; query_R = queries[i][1] - 1; query_K = queries[i][2]; document.write("Result for Query " + (i + 1) + " = " + answerQuery(query_L, query_R, query_K, P)+"<br>"); } } // Driver Code let arr=[8, 9, 1, 3]; let N = arr.length; /* queries[][] denotes the array of queries where each query has three integers query[i][0] -> Value of L for ith query query[i][0] -> Value of R for ith query query[i][0] -> Value of K for ith query */ let queries = [[1, 3, 4],[2, 4, 1]]; let Q = queries.length; answerQueries(queries, Q, arr, N); // This code is contributed by patel2127 </script>
Result for Query 1 = 2 Result for Query 2 = 3
La complejidad temporal de la construcción de la array de prefijos es O (N * número máximo de bits) y cada consulta se responde en O (1).
Espacio auxiliar : se requiere O(N * número máximo de bits) para construir la array de suma de prefijos