Dada la array de números enteros arr[] y consultas[] de tamaño N y Q , la tarea es encontrar el índice más grande para cada consulta Q[i] tal que bit a bit AND de cada elemento desde el inicio hasta ese índice sea al menos Q[i ], es decir (arr[1] & arr[2] &. . .& arr[k]) ≥ Q[i].
Ejemplo :
Entrada : arr[ ] = [3, 7, 9, 16] , queries[] = [ 2, 1 ]
Salida : 2 3
Explicación : La respuesta para la primera consulta es 2. Ya que, (3 & 7) = 3 >= 2. Entonces, el índice más grande es 2.
La respuesta para la segunda consulta es 3. Dado que, (3 & 7 & 9) = 1 >= 1. Entonces, el índice más grande es 3.Entrada : arr[ ] = [1, 2, 3], queries[ ] = [10]
Salida : -1
Explicación : Dado que la consulta 10 es grande, ninguno de los bit a bit Y el subarreglo de 1 a índice es posible,
por lo que la respuesta es -1.
Enfoque ingenuo : la idea básica del enfoque es iterar a través de la array arr[] para cada consulta y encontrar el índice más grande que cumpla con los criterios.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Inicialice una respuesta de array vacía para almacenar la respuesta a las consultas.
- Iterar de 0 a Q (digamos que el iterador es i ).
- Declare una variable llamada bit_and e inicialícela con arr[0].
- Si arr[0] es menor que X , agregue 0 a la respuesta y continúe
- Declare un conteo variable e inicialícelo con 1 para almacenar la respuesta para cada consulta.
- Iterar desde 1 hasta la longitud de arr (digamos que el iterador es j).
- Actualice bit_and con arr[j] & bit_and .
- Si bit_and es mayor que igual a X , incremente el conteo en 1 y continúe.
- De lo contrario, romper.
- Agregue el conteo a la respuesta .
- Devolver respuesta .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest index
vector<int> bitwiseAnd(int n, int q,
vector<int>& arr,
vector<int>& queries)
{
vector<int> answer;
for (int i = 0; i < q; i++) {
int x = queries[i];
int bit_and = arr[0];
if (arr[0] < x) {
answer.push_back(0);
continue;
}
int count = 1;
// Checking for the largest index
for (int j = 1; j < n; j++) {
bit_and = bit_and & arr[j];
if (bit_and >= x) {
count++;
continue;
}
else {
break;
}
}
answer.push_back(count);
}
return answer;
}
//Driver code
int main()
{
int N = 4, Q = 2;
vector<int> arr = { 3, 7, 9, 16 };
vector<int> queries = { 2, 1 };
// Function call
vector<int> ans
= bitwiseAnd(N, Q, arr, queries);
for (auto& i : ans)
cout << i << " ";
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the largest index
static ArrayList<Integer> bitwiseAnd(int n,int q,int[] arr,int[] queries)
{
ArrayList<Integer> answer = new ArrayList<Integer>();
for (int i = 0; i < q; i++) {
int x = queries[i];
int bit_and = arr[0];
if (arr[0] < x) {
answer.add(0);
continue;
}
int count = 1;
// Checking for the largest index
for (int j = 1; j < n; j++) {
bit_and = bit_and & arr[j];
if (bit_and >= x) {
count++;
continue;
}
else {
break;
}
}
answer.add(count);
}
return answer;
}
// Driver code
public static void main(String args[])
{
int N = 4, Q = 2;
int[] arr = {3, 7, 9, 16};
int[] queries = {2, 1};
// Function call
ArrayList<Integer>ans = bitwiseAnd(N, Q, arr, queries);
for (int i : ans)
System.out.printf("%d ",i);
}
}
// This code is contributed by shinjanpatra
Python3
# Python code for the above approach # Function to find the largest index def bitwiseAnd(n, q, arr,queries): answer =[] for i in range(q): x = queries[i] bit_and = arr[0] if (arr[0] < x) : answer.append(0) continue count = 1 # Checking for the largest index for j in range(1,n): bit_and = bit_and & arr[j] if (bit_and >= x): count += 1 continue else : break answer.append(count) return answer # Driver code N,Q = 4,2 arr = [3, 7, 9, 16] queries = [2, 1] # Function call ans = bitwiseAnd(N, Q, arr, queries) for i in ans : print(i,end=" ") # This code is contributed by shinjanpatra
C#
// C# program to implement above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the largest index
static void bitwiseAnd(int n, int q, int[]arr,
int[]queries)
{
List<int> answer = new List<int>();
for (int i = 0; i < q; i++) {
int x = queries[i];
int bit_and = arr[0];
if (arr[0] < x) {
answer.Add(0);
continue;
}
int count = 1;
// Checking for the largest index
for (int j = 1; j < n; j++) {
bit_and = bit_and & arr[j];
if (bit_and >= x) {
count++;
continue;
}
else {
break;
}
}
Console.Write(count + " ");
}
}
// Driver Code
public static void Main()
{
int N = 4, Q = 2;
int[] arr = { 3, 7, 9, 16 };
int[] queries = { 2, 1 };
// Function call
bitwiseAnd(N, Q, arr, queries);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the largest index
function bitwiseAnd(n, q, arr,
queries)
{
let answer =[];
for (let i = 0; i < q; i++) {
let x = queries[i];
let bit_and = arr[0];
if (arr[0] < x) {
answer.push(0);
continue;
}
let count = 1;
// Checking for the largest index
for (let j = 1; j < n; j++) {
bit_and = bit_and & arr[j];
if (bit_and >= x) {
count++;
continue;
}
else {
break;
}
}
answer.push(count);
}
return answer;
}
// Driver code
let N = 4, Q = 2;
let arr = [3, 7, 9, 16];
let queries = [2, 1];
// Function call
let ans
= bitwiseAnd(N, Q, arr, queries);
for ( i of ans)
document.write( i + " ");
// This code is contributed by Potta Lokesh
</script>
Producción
2 3
Complejidad temporal : O(N * Q)
Espacio auxiliar : O(1)
Enfoque eficiente : la idea de un enfoque eficiente se basa en la siguiente observación:
La operación AND bit a bit cuando se aplica desde el inicio de la array hasta el i-ésimo índice es monótonamente decreciente para una array. Por lo tanto, use la operación AND previa en la array y luego use la búsqueda binaria para encontrar el índice más grande que tenga un valor dado.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Declare una array vacía llamada respuesta para almacenar las respuestas a las consultas.
- Declare una array de tamaño N con nombre de prefijo para almacenar el prefijo Y de la array hasta el i-ésimo índice.
- Actualice el prefijo[0] con arr[0].
- Iterar de 1 a N (digamos que el iterador es j).
- Actualice prefix[j] con arr[j] & prefix[j-1] .
- Iterar de 0 a Q (digamos que el iterador es i).
- Declare 2 variables llamadas st y end e inicialícelas con 0 y N – 1 . Respectivamente.
- Declare una variable llamada cuenta e inicialícela con 0.
- Inicie un ciclo while con la condición st es menor que igual a END .
- Declare una variable llamada mid e inicialícela con ( st + end ) / 2.
- Si prefix[mid] es mayor que igual a queries[mid] , actualice count como mid+1 y st como mid+1 .
- De lo contrario, la actualización finaliza como mid-1 .
- Agregue el conteo a la respuesta.
- Devolver respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest index
vector<int> bitwiseAnd(int n, int q,
vector<int>& arr,
vector<int>& queries)
{
vector<int> answer;
vector<int> prefix(n, 0);
prefix[0] = arr[0];
// Constructing the prefix
// bitwise and array.
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] & arr[i];
}
for (int i = 0; i < q; i++) {
int x = queries[i];
int st = 0;
int end = n - 1;
int count = 0;
// Binary Searching the largest index
while (st <= end) {
int mid = (st + end) / 2;
if (prefix[mid] >= x) {
count = mid + 1;
st = mid + 1;
}
else {
end = mid - 1;
}
}
answer.push_back(count);
}
return answer;
}
// Driver code
int main()
{
int N = 4, Q = 2;
vector<int> arr = { 3, 7, 9, 16 };
vector<int> queries = { 2, 1 };
// Function call
vector<int> ans
= bitwiseAnd(N, Q, arr, queries);
for (auto& i : ans)
cout << i << " ";
return 0;
}
Java
// Java code to implement the approach
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the largest index
static ArrayList<Integer> bitwiseAnd(int n,int q,int[] arr,int[] queries)
{
ArrayList<Integer> answer = new ArrayList<Integer>();
ArrayList<Integer> prefix = new ArrayList<Integer>();
for(int i=0;i<n;i++)
{
prefix.add(0);
}
prefix.set(0,arr[0]);
// Constructing the prefix
// bitwise and array.
for (int i = 1; i < n; i++)
{
prefix.set(i,prefix.get(i-1) & arr[i]);
}
for (int i = 0; i < q; i++)
{
int x = queries[i];
int st = 0;
int end = n - 1;
int count = 0;
// Binary Searching the largest index
while (st <= end)
{
int mid = (st + end) / 2;
if (prefix.get(mid) >= x)
{
count = mid + 1;
st = mid + 1;
}
else
{
end = mid - 1;
}
}
answer.add(count);
}
return answer;
}
// Driver code
public static void main(String args[])
{
int N = 4, Q = 2;
int[] arr = {3, 7, 9, 16};
int[] queries = {2, 1};
// Function call
ArrayList<Integer>ans = bitwiseAnd(N, Q, arr, queries);
for (int i : ans)
System.out.printf("%d ",i);
}
}
// This code is contributed by aditya patil
Python3
# Python code to implement the approach # Function to find the largest index def bitwiseAnd (n, q, arr, queries): answer = [] prefix = [0]*n prefix[0] = arr[0] # Constructing the prefix # bitwise and array. for i in range(1,n): prefix[i] = prefix[i - 1] & arr[i] for i in range(q): x = queries[i] st = 0 end = n - 1 count = 0 # Binary Searching the largest index while (st <= end): mid = (st + end) // 2 if (prefix[mid] >= x): count = mid + 1 st = mid + 1 else: end = mid - 1 answer.append(count) return answer # Driver code N,Q = 4,2 arr = [3, 7, 9, 16] queries = [2, 1] # Function call ans = bitwiseAnd(N, Q, arr, queries) for i in ans: print(i,end=" ") # This code is contributed by shinjanpatra
C#
using System;
using System.Collections.Generic;
public class GFG {
// Driver Code
static public void Main()
{
int N = 4, Q = 2;
int[] arr = { 3, 7, 9, 16 };
int[] queries = { 2, 1 };
// Function call
int[] ans = bitwiseAnd(N, Q, arr, queries);
foreach(int i in ans) Console.Write(i + " ");
}
static int[] bitwiseAnd(int n, int q, int[] arr,
int[] queries)
{
List<int> answer = new List<int>();
int[] prefix = new int[n];
prefix[0] = arr[0];
// Constructing the prefix
// bitwise and array.
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] & arr[i];
}
for (int i = 0; i < q; i++) {
int x = queries[i];
int st = 0;
int end = n - 1;
int count = 0;
// Binary Searching the largest index
while (st <= end) {
int mid = (st + end) / 2;
if (prefix[mid] >= x) {
count = mid + 1;
st = mid + 1;
}
else {
end = mid - 1;
}
}
answer.Add(count);
}
return answer.ToArray();
}
}
// This code is contributed by Ishan Khandelwal
Javascript
<script>
// JavaScript code to implement the approach
// Function to find the largest index
const bitwiseAnd = (n, q, arr, queries) => {
let answer = [];
let prefix = new Array(n).fill(0);
prefix[0] = arr[0];
// Constructing the prefix
// bitwise and array.
for (let i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] & arr[i];
}
for (let i = 0; i < q; i++) {
let x = queries[i];
let st = 0;
let end = n - 1;
let count = 0;
// Binary Searching the largest index
while (st <= end) {
let mid = parseInt((st + end) / 2);
if (prefix[mid] >= x) {
count = mid + 1;
st = mid + 1;
}
else {
end = mid - 1;
}
}
answer.push(count);
}
return answer;
}
// Driver code
let N = 4, Q = 2;
let arr = [3, 7, 9, 16];
let queries = [2, 1];
// Function call
let ans = bitwiseAnd(N, Q, arr, queries);
for (let i in ans)
document.write(`${ans[i]} `);
// This code is contributed by rakeshsahni
</script>
Producción
2 3
Complejidad de tiempo : O(N+ Q* log N)
Espacio auxiliar : O(N)