Saltar al contenido

Encuentre el subarreglo más pequeño con Xor máximo de cualquier índice

Dada una matriz A[] que consiste en norte elementos, el trabajo es encontrar la longitud mínima del subarreglo de cada índice y el valor OR bit a bit es el máximo de todos los subarreglos posibles de ese índice.

Ejemplos:

Aporte: A[] = [4, 5, 2, 9, 11]
Salida: [4, 3, 2, 2, 1]
Explicación: Para i=0, subarreglo [4, 5, 2, 9] tiene un OR máximo de 15 y un tamaño mínimo de 4
Para i=1, subarreglo [5, 2, 9] tiene un OR máximo de 15 y un tamaño mínimo de 3
Para i=2, subarreglo [2, 9] tiene un OR máximo de 11 y un tamaño mínimo de 2
Para i=3, subarreglo [9, 11] tiene un OR máximo de 11 y un tamaño mínimo de 2
Para i=4, subarreglo [11] tiene un OR máximo de 11 y un tamaño mínimo de 1

Aporte: A[] = [7, 5, 2, 18, 11]
Salida: [5, 4, 3, 2, 1]

Enfoque ingenuo: La forma básica de resolver el problema es la siguiente:

Para cada imi El elemento iniciará un ciclo a partir de él para encontrar todos los subarreglos de ese índice y verificará el XOR máximo y el tamaño mínimo.

Siga los pasos a continuación para implementar la idea:

  • Empezar a iterar desde Yo = 0 a N-1:
    • Para cada índice, inicie un bucle anidado desde j = I a N-1:
      • Calcule el XOR bit a bit como el subarreglo [i, j] y actualice el XOR máximo y el tamaño mínimo en consecuencia.
    • Almacene el tamaño mínimo en una matriz.
  • Devuelve la matriz como la respuesta requerida.

A continuación encontrará la implementación del enfoque anterior.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

vector<int> MaxBitWiseOR_Array(vector<int>& nums)

{

    int n = nums.size();

    if (n == 1 and nums[0] == 0)

        return { 1 };

    vector<int> mor(n), ans(n);

    mor[n - 1] = nums[n - 1];

    for (int i = n - 2; i >= 0; i--)

        mor[i] = mor[i + 1] | nums[i];

    for (int i = 0; i < n; i++) {

        int j = i;

        int x = 0;

        while (j < n and x != mor[i]) {

            x |= nums[j];

            j++;

        }

        if (j < n and nums[j] == 0 and i == j)

            j++;

        ans[i] = j - i;

    }

    return ans;

}

 

int main()

{

    vector<int> Arr = { 4, 5, 2, 9, 11 };

 

    

    vector<int> ans = MaxBitWiseOR_Array(Arr);

    for (int i = 0; i < ans.size(); i++)

        cout << ans[i] << " ";

 

    return 0;

}

Complejidad del tiempo: A2)
cuarto auxiliar: A)

Enfoque eficiente: Siga los pasos a continuación para resolver el problema:

Crearemos una matriz para almacenar la última ocurrencia de un conjunto de bits del máximo posible OR para imi elemento en la matriz y el imi el resultado es la diferencia máxima en el índice de cada bit establecido y el índice actual.

Siga los pasos a continuación para implementar la idea:

  • Cruce I = N-1 a 0:
    • Para cada matriz, recorra todos los bits de j = 0 a 32:
      • si ymi bit se configuró previamente y también se configuró en el elemento actual, actualice la última instancia de jmi un poco.
      • si tumi bit se estableció previamente, pero no en el elemento actual, entonces el bit jth también se establece como respuesta.
      • Actualice la longitud máxima como el máximo entre la longitud máxima y la diferencia entre el índice de ymi establecer bit y . en i.
      • si tumi bit no se configuró antes, configure el jmi bit y actualice la última instancia.
    • La longitud máxima calculada de esta manera es la respuesta para este índice. Guárdelo en una matriz.
  • Devuelve la matriz como la respuesta requerida.

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

C++

#include <bits/stdc++.h>

using namespace std;

 

vector<int> MaxBitWiseOR_Array(vector<int>& nums)

{

    int n = nums.size();

    vector<int> res(n, 1);

    vector<int> latest(32);

    for (int i = n - 1; i >= 0; i--) {

        for (int j = 0; j < 32; j++) {

            if (nums[i] & (1 << j))

                latest[j] = i;

            res[i] = max(res[i], latest[j] - i + 1);

        }

    }

    return res;

}

 

int main()

{

    vector<int> Arr = { 4, 5, 2, 9, 11 };

 

    

    vector<int> ans = MaxBitWiseOR_Array(Arr);

    for (int i = 0; i < ans.size(); i++)

        cout << ans[i] << " ";

}

Complejidad del tiempo: O(32*N)
cuarto auxiliar: O(32)