Dada una array arr[] que consta de enteros positivos y una array Q[][] que consta de consultas, la tarea para cada i -ésima consulta es contar los elementos de la array del rango [Q[i][0], Q[i] [1]] con solo un bit establecido.
Ejemplos:
Entrada: arr[] = {12, 11, 16, 8, 2, 5, 1, 3, 256, 1}, consultas[][] = {{0, 9}, {4, 9}}
Salida: 6 4
Explicación:
En el rango de índices [0, 9], los elementos arr[2] (= 16), arr[3](= 8), arr[4]( = 2), arr[6](= 1 ), arr[8](= 256), arr[9](= 1) tienen solo 1 bit establecido.
En el rango [4, 9], los elementos arr[4] (= 2), arr[6](= 1), arr[8](= 256), arr[9] (= 1) tienen solo 1 conjunto un poco.Entrada: arr[] = {2, 1, 101, 11, 4}, consultas[][] = {{2, 4}, {1, 4}}
Salida: 1 2
Enfoque ingenuo: el enfoque más simple para cada consulta es iterar el rango [l, r] y contar la cantidad de elementos de la array que tienen solo un bit establecido mediante el algoritmo de Brian Kernighan .
Complejidad de tiempo : O(Q * N*logN)
Espacio auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice una array de suma de prefijos para almacenar la cantidad de elementos con solo un bit establecido.
- El índice i-ésimo almacena el recuento de elementos de array con solo un bit establecido hasta el índice i -ésimo .
- Para cada consulta (i, j) , devuelve pre[j] – pre[i – 1] , es decir ( principio de inclusión-exclusión ).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether // only one bit is set or not int check(int x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query int query(int l, int r, int pre[]) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query void countInRange(int arr[], int N, vector<pair<int, int> > queries, int Q) { // Initialize array for Prefix sum int pre[N] = { 0 }; pre[0] = check(arr[0]); for (int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; while (Q--) { int l = queries.first; int r = queries.second; c++; cout << query(l, r, pre) << ' '; } } // Driver Code int main() { // Given array int arr[] = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Given queries vector<pair<int, int> > queries = { { 0, 9 }, { 4, 9 } }; // Size of queries array int Q = queries.size(); countInRange(arr, N, queries, Q); return 0; }
Java
// JAVA program for the above approach import java.util.*; import java.io.*; import java.math.*; public class GFG { // Function to check whether // only one bit is set or not static int check(int x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query static int query(int l, int r, int[] pre) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query static void countInRange(int[] arr, int N, ArrayList<Pair> queries, int Q) { // Initialize array for Prefix sum int[] pre = new int[N]; pre[0] = check(arr[0]); for(int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; int q = 0; while (q < Q) { int l = queries.get(q).item1; int r = queries.get(q).item2; c++; q++; System.out.print(query(l, r, pre) + " "); } } // A Pair class for handling queries in JAVA // As, there is no in-built function of Tuple static class Pair { int item1, item2; Pair(int item1, int item2) { this.item1 = item1; this.item2 = item2; } } // Driver code public static void main(String args[]) { // Given array int[] arr = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = arr.length; // Given queries ArrayList<Pair> queries = new ArrayList<Pair>(); queries.add(new Pair(4,9)); queries.add(new Pair(0,9)); // Size of queries array int Q = queries.size(); countInRange(arr, N, queries, Q); } } // This code is contributed by jyoti369
Python3
# Python 3 program for the above approach # Function to check whether # only one bit is set or not def check(x): if (((x) & (x - 1)) == 0): return 1 return 0 # Function to perform Range-query def query(l, r, pre): if (l == 0): return pre[r] else: return pre[r] - pre[l - 1] # Function to count array elements with a # single set bit for each range in a query def countInRange(arr, N, queries, Q): # Initialize array for Prefix sum pre = [0] * N pre[0] = check(arr[0]) for i in range(1, N): pre[i] = pre[i - 1] + check(arr[i]) c = 0 while (Q > 0): l = queries[0] r = queries[1] c += 1 print(query(l, r, pre), end=" ") Q -= 1 # Driver Code if __name__ == "__main__": # Given array arr = [12, 11, 16, 8, 2, 5, 1, 3, 256, 1] # Size of the array N = len(arr) # Given queries queries = [[0, 9], [4, 9]] # Size of queries array Q = len(queries) countInRange(arr, N, queries, Q) # this code is contributed by chitranayal.
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to check whether // only one bit is set or not static int check(int x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query static int query(int l, int r, int[] pre) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query static void countInRange(int[] arr, int N, List<Tuple<int, int>> queries, int Q) { // Initialize array for Prefix sum int[] pre = new int[N]; pre[0] = check(arr[0]); for(int i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } int c = 0; int q = 0; while (q < Q) { int l = queries[q].Item1; int r = queries[q].Item2; c++; q++; Console.Write(query(l, r, pre) + " "); } } // Driver code static void Main() { // Given array int[] arr = { 12, 11, 16, 8, 2, 5, 1, 3, 256, 1 }; // Size of the array int N = arr.Length; // Given queries List<Tuple<int, int>> queries = new List<Tuple<int, int>>(); queries.Add(new Tuple<int, int>(0, 9)); queries.Add(new Tuple<int, int>(4, 9)); // Size of queries array int Q = queries.Count; countInRange(arr, N, queries, Q); } } // This code is contributed by divyeshrabadiya07
Javascript
<script> // JavaScript program for the above approach // Function to check whether // only one bit is set or not function check(x) { if (((x) & (x - 1)) == 0) return 1; return 0; } // Function to perform Range-query function query(l, r, pre) { if (l == 0) return pre[r]; else return pre[r] - pre[l - 1]; } // Function to count array elements with a // single set bit for each range in a query function countInRange(arr, N, queries, Q) { // Initialize array for Prefix sum var pre = Array(N).fill(0); pre[0] = check(arr[0]); for (var i = 1; i < N; i++) { pre[i] = pre[i - 1] + check(arr[i]); } var c = 0; while (Q--) { var l = queries[0]; var r = queries[1]; c++; document.write( query(l, r, pre) + ' '); } } // Driver Code // Given array var arr = [12, 11, 16, 8, 2, 5, 1, 3, 256, 1]; // Size of the array var N = arr.length; // Given queries var queries = [[0, 9], [4, 9 ]]; // Size of queries array var Q = queries.length; countInRange(arr, N, queries, Q); </script>
6 4
Complejidad de tiempo: O(N*log(max(arr[i])))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prakersh009 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA