Subarreglo de longitud mínima a partir de cada índice con OR máximo

Dada una array de tamaño N . Considere todos los subarreglos que comienzan en cada índice desde [0, N – 1]. Determine la longitud del subarreglo más pequeño a partir de cada índice cuyo OR bit a bit sea máximo.

Ejemplos:

Entrada: N = 5, A = {1, 2, 3, 4, 5}
Salida: {4, 3, 2, 2, 1}
Explicación: 

• Para i = 1 y el tamaño del subarreglo = 1, la puntuación de este subarreglo es 1. 
  Para el tamaño = 2, el valor es 1 | 2 = 3. 
  Para tamaño = 3, el valor es 1 | 2 | 3 = 3.
  Para tamaño = 4, el valor es 1 | 2 | 3 | 4 = 7 y 
  para tamaño = 5, el valor de este subarreglo es 1 | 2 | 3 | 4 | 5 = 7. 
  Puede ver que el valor máximo es 7, y el tamaño más pequeño 
  del subarreglo que comienza en 1 con este valor es de tamaño 4. 
  Por lo tanto, la respuesta máxima a partir del primer índice es igual a 4.
• Para i = 2 y tamaño = 1, el valor es 2. 
  Para tamaño = 2, el valor es 2 | 3 = 3. 
  Para tamaño = 3, el valor es 2 | 3 | 4 = 7. 
  Para tamaño = 4, el valor es 2 | 3 | 4 | 5 = 7. 
  Puede ver que la puntuación máxima es 7, y el tamaño más pequeño 
  del subarreglo que comienza en 2, con este valor es de tamaño 3. 
  Entonces, la respuesta máxima a partir del segundo índice es igual a 3.
• Para i = 3 y tamaño = 1, el valor es 3. 
  Para tamaño = 2, el valor es 3 | 4 = 7. 
  Para tamaño = 3, el valor es 3 | 4 | 5 = 7. 
  Así que para i = 3 el tamaño es 2
• Para i = 4 y tamaño = 1, la puntuación es 4 y para tamaño = 2, la puntuación es 4 | 1 = 5. 
  Entonces el tamaño es igual a 2.
• Para i = 5 solo hay un subarreglo de tamaño 1.

Entrada: N = 7, A = {2, 4, 3, 1, 5, 4, 6}
Salida: {3, 2, 3, 4, 3, 2, 1}

Enfoque ingenuo: para resolver el problema, siga la siguiente idea:

Para cada índice, encuentre todos los subarreglos a partir de ese índice y encuentre el más pequeño con OR bit a bit máximo.

Siga los pasos dados para resolver el problema utilizando el enfoque anterior:

• Recorra la array usando dos bucles for anidados, para encontrar todos los subarreglos posibles
• Calcule el valor OR de cada subarreglo y actualice la respuesta máxima encontrada hasta ahora para el índice inicial actual.
• Empuje el tamaño de subarreglo de longitud mínima, con el valor máximo en el arreglo de respuesta.
• Devuelve la array de respuesta.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// This function is for finding the minimum
// length maximum OR subarray, for each index
vector<int> solve(int arr[], int N)
{
    vector<int> len;
 
    for (int i = 0; i < N; i++) {
        int mxor = 0, mnlen = 0, OR = 0;
        for (int j = i; j < N; j++) {
            OR = OR | arr[j];
 
            // Updating maximum value found
            // so far
            if (mxor < OR) {
                mxor = OR;
                mnlen = j - i + 1;
            }
        }
        len.push_back(mnlen);
    }
 
    return len;
}
 
// Driver's code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    vector<int> mnlen = solve(arr, N);
 
    for (int i = 0; i < N; i++)
        cout << mnlen[i] << " ";
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
 
  // This function is for finding the minimum length
  // maximum OR subarray, for each index
  static List<Integer> solve(int[] arr, int N)
  {
    List<Integer> len = new ArrayList<>();
 
    for (int i = 0; i < N; i++) {
      int mxor = 0, mnlen = 0, OR = 0;
      for (int j = i; j < N; j++) {
        OR = OR | arr[j];
 
        // Updating maximum value found so far
        if (mxor < OR) {
          mxor = OR;
          mnlen = j - i + 1;
        }
      }
      len.add(mnlen);
    }
    return len;
  }
 
  public static void main(String[] args)
  {
    int[] arr = { 1, 2, 3, 4, 5 };
    int N = arr.length;
 
    // Function call
    List<Integer> mnlen = solve(arr, N);
 
    for (int i = 0; i < N; i++) {
      System.out.print(mnlen.get(i) + " ");
    }
  }
}
 
// This code is contributed by lokesh (lokeshmvs21).

4 3 2 2 1 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: para resolver el problema, siga la siguiente idea:

Al observar la funcionalidad de OR, los bits solo se pueden activar usando 1. Entonces, comience desde el final y realice un seguimiento del índice mínimo que mantendrá el bit en particular como un conjunto y luego tomamos un máximo de todos los índices que contienen los bits establecidos.

Siga los pasos dados para resolver el problema utilizando el enfoque anterior:

• Recorra la array dada desde el final y actualice el índice mínimo de cada bit establecido en el elemento actual
• Tome el índice máximo de todos los bits establecidos hasta el momento, como la respuesta para el índice actual.
• Devuelve la array de respuesta

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// This function is for finding the
// minimum length maximum OR subarray
vector<int> solve(int arr[], int N)
{
    vector<int> ans;
    vector<int> nearest(32, -1);
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < 32; j++) {
 
            // Nearest index where jth
            // bit is set
            if (arr[i] & (1 << j))
                nearest[j] = i;
        }
 
        int last_set_bit_index = i;
 
        // Finding Maximum index of all set bits
        for (int j = 0; j < 32; j++)
            last_set_bit_index
                = max(last_set_bit_index, nearest[j]);
 
        ans.push_back(last_set_bit_index - i + 1);
    }
 
    // Reversing the answer vector
    reverse(ans.begin(), ans.end());
    return ans;
}
 
// Driver code
int main()
{
 
    int arr[] = { 1, 2, 3, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    vector<int> mnlen = solve(arr, N);
    for (int i = 0; i < N; i++)
        cout << mnlen[i] << " ";
    return 0;
}

<script>
    // JavaScript program for the above approach
 
    // This function is for finding the
    // minimum length maximum OR subarray
    const solve = (arr, N) => {
        let ans = [];
        let nearest = new Array(32).fill(-1);
        for (let i = N - 1; i >= 0; i--) {
            for (let j = 0; j < 32; j++) {
 
                // Nearest index where jth
                // bit is set
                if (arr[i] & (1 << j))
                    nearest[j] = i;
            }
 
            let last_set_bit_index = i;
 
            // Finding Maximum index of all set bits
            for (let j = 0; j < 32; j++)
                last_set_bit_index
                    = Math.max(last_set_bit_index, nearest[j]);
 
            ans.push(last_set_bit_index - i + 1);
        }
 
        // Reversing the answer vector
        ans.reverse();
        return ans;
    }
 
    // Driver code
    let arr = [1, 2, 3, 4, 5];
    let N = arr.length;
 
    // Function call
    let mnlen = solve(arr, N);
    for (let i = 0; i < N; i++)
        document.write(`${mnlen[i]} `);
 
    // This code is contributed by rakeshsahni
 
</script>

4 3 2 2 1 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)