Dada una array arr[] de enteros positivos y un número K , la tarea es encontrar los valores mínimo y máximo de la operación Bitwise en elementos de subarreglo de tamaño K.
Ejemplos:
Entrada: arr[]={2, 5, 3, 6, 11, 13}, k = 3
Salida:
AND máximo = 2
AND mínimo = 0
OR máximo = 15
OR mínimo = 7
Explicación:
AND máximo es generado por el subarreglo 3 , 6 y 11, 3 y 6 y 11 = 2
El mínimo AND lo genera el subarreglo 2, 3 y 5, 2 y 3 y 5 = 0
El máximo OR lo genera el subarreglo 2, 6 y 13, 2 | 6 | 13 = 15
OR mínimo es generado por el subarreglo 2, 3 y 5, 2 | 3 | 5 = 7Entrada: arr[]={5, 9, 7, 19}, k = 2
Salida:
Máximo AND = 3
Mínimo AND = 1
Máximo OR = 23
Mínimo OR = 13
Enfoque ingenuo: el enfoque ingenuo es generar todos los subarreglos posibles de tamaño K y verificar cuál de los subarreglos formados anteriormente dará el OR y AND bit a bit mínimo y máximo.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(K)
Enfoque eficiente: la idea es utilizar la técnica de la ventana deslizante para resolver este problema. A continuación se muestran los pasos:
- Recorra la array de prefijos de tamaño K y para cada array, el elemento pasa por cada bit y aumenta la array de bits (manteniendo un bit de array entera de tamaño 32) en 1 si está configurado.
- Convierta esta array de bits en un número decimal, digamos ans , y mueva la ventana deslizante al siguiente índice.
- Para el elemento recién agregado para el siguiente subarreglo de tamaño K , itere a través de cada bit del elemento recién agregado y aumente el conjunto de bits en 1 si está configurado.
- Para eliminar el primer elemento de la ventana anterior, disminuya la array de bits en 1 si está configurada.
- Actualice ans con un mínimo o máximo del nuevo número decimal generado por la array de bits.
- A continuación se muestra el programa para encontrar el subarreglo OR bit a bit máximo :
C++
// C++ program for maximum values of
// each bitwise OR operation on
// element of subarray of size K
#include <iostream>
using namespace std;
// Function to convert bit array to
// decimal number
int build_num(int bit[])
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i])
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise OR operation on
// element of subarray of size K
int maximumOR(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[32] = { 0 };
// Create a sliding window of size k
for (int i = 0; i < k; i++) {
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
}
// Function call
int max_or = build_num(bit);
for (int i = k; i < n; i++) {
// Perform operation for
// removed element
for (int j = 0; j < 32; j++) {
if (arr[i - k] & (1 << j))
bit[j]--;
}
// Perform operation for
// added_element
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
// Taking maximum value
max_or = max(build_num(bit), max_or);
}
// Return the result
return max_or;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << maximumOR(arr, n, k);
return 0;
}
Java
// Java program for maximum values of
// each bitwise OR operation on
// element of subarray of size K
import java.util.*;
class GFG{
// Function to convert bit array to
// decimal number
static int build_num(int bit[])
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise OR operation on
// element of subarray of size K
static int maximumOR(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[] = new int[32];
// Create a sliding window of size k
for (int i = 0; i < k; i++)
{
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int max_or = build_num(bit);
for (int i = k; i < n; i++)
{
// Perform operation for
// removed element
for (int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_or = Math.max(build_num(bit), max_or);
}
// Return the result
return max_or;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.length;
// Function Call
System.out.print(maximumOR(arr, n, k));
}
}
// This code is contributed by Rohit_ranjan
Python3
# Python3 program for maximum values of # each bitwise OR operation on # element of subarray of size K # Function to convert bit array to # decimal number def build_num(bit): ans = 0; for i in range(32): if (bit[i] > 0): ans += (1 << i); return ans; # Function to find maximum values of # each bitwise OR operation on # element of subarray of size K def maximumOR(arr, n, k): # Maintain an integer array bit # of size 32 all initialized to 0 bit = [0] * 32; # Create a sliding window of size k for i in range(k): for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Function call max_or = build_num(bit); for i in range(k, n): # Perform operation for # removed element for j in range(32): if ((arr[i - k] & (1 << j)) > 0): bit[j] -= 1; # Perform operation for # added_element for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Taking maximum value max_or = max(build_num(bit), max_or); # Return the result return max_or; # Driver Code if __name__ == '__main__': # Given array arr arr = [ 2, 5, 3, 6, 11, 13 ]; # Given subarray size K k = 3; n = len(arr); # Function call print(maximumOR(arr, n, k)); # This code is contributed by Amit Katiyar
C#
// C# program for maximum values of
// each bitwise OR operation on
// element of subarray of size K
using System;
class GFG{
// Function to convert bit
// array to decimal number
static int build_num(int[] bit)
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise OR operation on
// element of subarray of size K
static int maximumOR(int[] arr, int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int[] bit = new int[32];
// Create a sliding window of size k
for (int i = 0; i < k; i++)
{
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int max_or = build_num(bit);
for (int i = k; i < n; i++)
{
// Perform operation for
// removed element
for (int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_or = Math.Max(build_num(bit), max_or);
}
// Return the result
return max_or;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {2, 5, 3, 6, 11, 13};
// Given subarray size K
int k = 3;
int n = arr.Length;
// Function Call
Console.Write(maximumOR(arr, n, k));
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// Javascript program for maximum values of
// each bitwise OR operation on
// element of subarray of size K
// Function to convert bit array to
// decimal number
function build_num(bit)
{
let ans = 0;
for (let i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise OR operation on
// element of subarray of size K
function maximumOR(arr, n, k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
let bit = new Array(32);
bit.fill(0);
// Create a sliding window of size k
for (let i = 0; i < k; i++)
{
for (let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
let max_or = build_num(bit);
for (let i = k; i < n; i++)
{
// Perform operation for
// removed element
for (let j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for (let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_or = Math.max(build_num(bit), max_or);
}
// Return the result
return max_or;
}
// Given array []arr
let arr = [2, 5, 3, 6, 11, 13];
// Given subarray size K
let k = 3;
let n = arr.length;
// Function Call
document.write(maximumOR(arr, n, k));
// This code is contributed by divyesh072019.
</script>
Producción:
15
Complejidad de tiempo: O(n * B) donde n es el tamaño de la array y B es el bit de array entera de tamaño 32.
Espacio auxiliar: O(n)
- A continuación se muestra el programa para encontrar el subarreglo OR mínimo bit a bit :
C++
// C++ program for minimum values of
// each bitwise OR operation on
// element of subarray of size K
#include <iostream>
using namespace std;
// Function to convert bit array
// to decimal number
int build_num(int bit[])
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i])
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise OR operation on
// element of subarray of size K
int minimumOR(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[32] = { 0 };
// Create a sliding window of size k
for (int i = 0; i < k; i++) {
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
}
// Function call
int min_or = build_num(bit);
for (int i = k; i < n; i++) {
// Perform operation for
// removed element
for (int j = 0; j < 32; j++) {
if (arr[i - k] & (1 << j))
bit[j]--;
}
// Perform operation for
// added_element
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
// Taking minimum value
min_or = min(build_num(bit),
min_or);
}
// Return the result
return min_or;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << minimumOR(arr, n, k);
return 0;
}
Java
// Java program for minimum values of
// each bitwise OR operation on
// element of subarray of size K
import java.util.*;
class GFG{
// Function to convert bit array
// to decimal number
static int build_num(int bit[])
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise OR operation on
// element of subarray of size K
static int minimumOR(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[] = new int[32];
// Create a sliding window of size k
for(int i = 0; i < k; i++)
{
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int min_or = build_num(bit);
for(int i = k; i < n; i++)
{
// Perform operation for
// removed element
for(int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_or = Math.min(build_num(bit),
min_or);
}
// Return the result
return min_or;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.length;
// Function call
System.out.print(minimumOR(arr, n, k));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for minimum values # of each bitwise OR operation on # element of subarray of size K # Function to convert bit array # to decimal number def build_num(bit): ans = 0; for i in range(32): if (bit[i] > 0): ans += (1 << i); return ans; # Function to find minimum values of # each bitwise OR operation on # element of subarray of size K def minimumOR(arr, n, k): # Maintain an integer array bit # of size 32 all initialized to 0 bit = [0] * 32; # Create a sliding window of size k for i in range(k): for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Function call min_or = build_num(bit); for i in range(k, n): # Perform operation for # removed element for j in range(32): if ((arr[i - k] & (1 << j)) > 0): bit[j] -= 1; # Perform operation for # added_element for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Taking minimum value min_or = min(build_num(bit), min_or); # Return the result return min_or; # Driver Code if __name__ == '__main__': # Given array arr arr = [ 2, 5, 3, 6, 11, 13 ]; # Given subarray size K k = 3; n = len(arr); # Function call print(minimumOR(arr, n, k)); # This code is contributed by Amit Katiyar
C#
// C# program for minimum values of
// each bitwise OR operation on
// element of subarray of size K
using System;
class GFG{
// Function to convert bit array
// to decimal number
static int build_num(int []bit)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise OR operation on
// element of subarray of size K
static int minimumOR(int []arr, int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int []bit = new int[32];
// Create a sliding window of size k
for(int i = 0; i < k; i++)
{
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int min_or = build_num(bit);
for(int i = k; i < n; i++)
{
// Perform operation for
// removed element
for(int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_or = Math.Min(build_num(bit),
min_or);
}
// Return the result
return min_or;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.Length;
// Function call
Console.Write(minimumOR(arr, n, k));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for minimum values of
// each bitwise OR operation on
// element of subarray of size K
// Function to convert bit array
// to decimal number
function build_num(bit)
{
let ans = 0;
for(let i = 0; i < 32; i++)
if (bit[i] > 0)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise OR operation on
// element of subarray of size K
function minimumOR(arr, n, k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
let bit = new Array(32);
bit.fill(0);
// Create a sliding window of size k
for(let i = 0; i < k; i++)
{
for(let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
let min_or = build_num(bit);
for(let i = k; i < n; i++)
{
// Perform operation for
// removed element
for(let j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added_element
for(let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_or = Math.min(build_num(bit), min_or);
}
// Return the result
return min_or;
}
// Driver code
// Given array arr[]
let arr = [ 2, 5, 3, 6, 11, 13 ];
// Given subarray size K
let k = 3;
let n = arr.length;
// Function Call
document.write(minimumOR(arr, n, k));
// This code is contributed by rameshtravel07
</script>
Producción:
7
Complejidad de tiempo: O(n * B) donde n es el tamaño de la array y B es el bit de array entera de tamaño 32.
Espacio auxiliar: O(n)
- A continuación se muestra el programa para encontrar el subarreglo AND bit a bit máximo :
C++
// C++ program for maximum values of
// each bitwise AND operation on
// element of subarray of size K
#include <iostream>
using namespace std;
// Function to convert bit array
// to decimal number
int build_num(int bit[], int k)
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise AND operation on
// element of subarray of size K
int maximumAND(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[32] = { 0 };
// Create a sliding window of size k
for (int i = 0; i < k; i++) {
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
}
// Function call
int max_and = build_num(bit, k);
for (int i = k; i < n; i++) {
// Perform operation for
// removed element
for (int j = 0; j < 32; j++) {
if (arr[i - k] & (1 << j))
bit[j]--;
}
// Perform operation for
// added element
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
// Taking maximum value
max_and = max(build_num(bit, k),
max_and);
}
// Return the result
return max_and;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << maximumAND(arr, n, k);
return 0;
}
Java
// Java program for maximum values of
// each bitwise AND operation on
// element of subarray of size K
class GFG{
// Function to convert bit array
// to decimal number
static int build_num(int bit[], int k)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise AND operation on
// element of subarray of size K
static int maximumAND(int arr[],
int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[] = new int[32];
// Create a sliding window of size k
for(int i = 0; i < k; i++)
{
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int max_and = build_num(bit, k);
for(int i = k; i < n; i++)
{
// Perform operation for
// removed element
for(int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added element
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_and = Math.max(build_num(bit, k),
max_and);
}
// Return the result
return max_and;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.length;
// Function call
System.out.print(maximumAND(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for maximum values of # each bitwise AND operation on # element of subarray of size K # Function to convert bit array # to decimal number def build_num(bit, k): ans = 0; for i in range(32): if (bit[i] == k): ans += (1 << i); return ans; # Function to find maximum values of # each bitwise AND operation on # element of subarray of size K def maximumAND(arr, n, k): # Maintain an integer array bit # of size 32 all initialized to 0 bit = [0] * 32; # Create a sliding window of size k for i in range(k): for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Function call max_and = build_num(bit, k); for i in range(k, n): # Perform operation for # removed element for j in range(32): if ((arr[i - k] & (1 << j)) > 0): bit[j] -= 1; # Perform operation for # added element for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Taking maximum value max_and = max(build_num(bit, k), max_and); # Return the result return max_and; # Driver Code if __name__ == '__main__': # Given array arr arr = [ 2, 5, 3, 6, 11, 13 ]; # Given subarray size K k = 3; n = len(arr); # Function call print(maximumAND(arr, n, k)); # This code is contributed by Amit Katiyar
C#
// C# program for maximum values of
// each bitwise AND operation on
// element of subarray of size K
using System;
class GFG{
// Function to convert bit
// array to decimal number
static int build_num(int[] bit, int k)
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise AND operation on
// element of subarray of size K
static int maximumAND(int[] arr, int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int[] bit = new int[32];
// Create a sliding window of size k
for (int i = 0; i < k; i++)
{
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int max_and = build_num(bit, k);
for (int i = k; i < n; i++)
{
// Perform operation for
// removed element
for (int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added element
for (int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_and = Math.Max(build_num(bit, k),
max_and);
}
// Return the result
return max_and;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int[] arr = {2, 5, 3, 6, 11, 13};
// Given subarray size K
int k = 3;
int n = arr.Length;
// Function call
Console.Write(maximumAND(arr, n, k));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for maximum values of
// each bitwise AND operation on
// element of subarray of size K
// Function to convert bit
// array to decimal number
function build_num(bit, k)
{
let ans = 0;
for (let i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find maximum values of
// each bitwise AND operation on
// element of subarray of size K
function maximumAND(arr, n, k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
let bit = new Array(32);
bit.fill(0);
// Create a sliding window of size k
for (let i = 0; i < k; i++)
{
for (let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
let max_and = build_num(bit, k);
for (let i = k; i < n; i++)
{
// Perform operation for
// removed element
for (let j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation for
// added element
for (let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking maximum value
max_and = Math.max(build_num(bit, k),
max_and);
}
// Return the result
return max_and;
}
// Given array []arr
let arr = [2, 5, 3, 6, 11, 13];
// Given subarray size K
let k = 3;
let n = arr.length;
// Function call
document.write(maximumAND(arr, n, k));
// This code is contributed by mukesh07.
</script>
Producción:
2
Complejidad de tiempo: O(n * B) donde n es el tamaño de la array y B es el bit de array entera de tamaño 32.
Espacio auxiliar: O(n)
- A continuación se muestra el programa para encontrar el subarreglo AND bit a bit mínimo :
C++
// C++ program for minimum values of
// each bitwise AND operation on
// elements of subarray of size K
#include <iostream>
using namespace std;
// Function to convert bit array
// to decimal number
int build_num(int bit[], int k)
{
int ans = 0;
for (int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise AND operation on
// element of subarray of size K
int minimumAND(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[32] = { 0 };
// Create a sliding window of size k
for (int i = 0; i < k; i++) {
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
}
// Function call
int min_and = build_num(bit, k);
for (int i = k; i < n; i++) {
// Perform operation to removed
// element
for (int j = 0; j < 32; j++) {
if (arr[i - k] & (1 << j))
bit[j]--;
}
// Perform operation to add
// element
for (int j = 0; j < 32; j++) {
if (arr[i] & (1 << j))
bit[j]++;
}
// Taking minimum value
min_and = min(build_num(bit, k),
min_and);
}
// Return the result
return min_and;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = sizeof arr / sizeof arr[0];
// Function Call
cout << minimumAND(arr, n, k);
return 0;
}
Java
// Java program for minimum values of
// each bitwise AND operation on
// elements of subarray of size K
class GFG{
// Function to convert bit array
// to decimal number
static int build_num(int bit[], int k)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise AND operation on
// element of subarray of size K
static int minimumAND(int arr[], int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int bit[] = new int[32];
// Create a sliding window of size k
for(int i = 0; i < k; i++)
{
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int min_and = build_num(bit, k);
for(int i = k; i < n; i++)
{
// Perform operation to removed
// element
for(int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation to add
// element
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_and = Math.min(build_num(bit, k),
min_and);
}
// Return the result
return min_and;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.length;
// Function call
System.out.print(minimumAND(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for minimum values of # each bitwise AND operation on # elements of subarray of size K # Function to convert bit array # to decimal number def build_num(bit, k): ans = 0; for i in range(32): if (bit[i] == k): ans += (1 << i); return ans; # Function to find minimum values of # each bitwise AND operation on # element of subarray of size K def minimumAND(arr, n, k): # Maintain an integer array bit # of size 32 all initialized to 0 bit = [0] * 32; # Create a sliding window of size k for i in range(k): for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Function call min_and = build_num(bit, k); for i in range(k, n): # Perform operation to removed # element for j in range(32): if ((arr[i - k] & (1 << j)) > 0): bit[j] -=1; # Perform operation to add # element for j in range(32): if ((arr[i] & (1 << j)) > 0): bit[j] += 1; # Taking minimum value min_and = min(build_num(bit, k), min_and); # Return the result return min_and; # Driver Code if __name__ == '__main__': # Given array arr arr = [2, 5, 3, 6, 11, 13]; # Given subarray size K k = 3; n = len(arr); # Function call print(minimumAND(arr, n, k)); # This code contributed by Rajput-Ji
C#
// C# program for minimum values of
// each bitwise AND operation on
// elements of subarray of size K
using System;
class GFG{
// Function to convert bit array
// to decimal number
static int build_num(int []bit, int k)
{
int ans = 0;
for(int i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise AND operation on
// element of subarray of size K
static int minimumAND(int []arr, int n, int k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
int []bit = new int[32];
// Create a sliding window of size k
for(int i = 0; i < k; i++)
{
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
int min_and = build_num(bit, k);
for(int i = k; i < n; i++)
{
// Perform operation to removed
// element
for(int j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation to add
// element
for(int j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_and = Math.Min(build_num(bit, k),
min_and);
}
// Return the result
return min_and;
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 2, 5, 3, 6, 11, 13 };
// Given subarray size K
int k = 3;
int n = arr.Length;
// Function call
Console.Write(minimumAND(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for minimum values of
// each bitwise AND operation on
// elements of subarray of size K
// Function to convert bit array
// to decimal number
function build_num(bit, k)
{
let ans = 0;
for(let i = 0; i < 32; i++)
if (bit[i] == k)
ans += (1 << i);
return ans;
}
// Function to find minimum values of
// each bitwise AND operation on
// element of subarray of size K
function minimumAND(arr, n, k)
{
// Maintain an integer array bit[]
// of size 32 all initialized to 0
let bit = new Array(32);
bit.fill(0);
// Create a sliding window of size k
for(let i = 0; i < k; i++)
{
for(let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
}
// Function call
let min_and = build_num(bit, k);
for(let i = k; i < n; i++)
{
// Perform operation to removed
// element
for(let j = 0; j < 32; j++)
{
if ((arr[i - k] & (1 << j)) > 0)
bit[j]--;
}
// Perform operation to add
// element
for(let j = 0; j < 32; j++)
{
if ((arr[i] & (1 << j)) > 0)
bit[j]++;
}
// Taking minimum value
min_and = Math.min(build_num(bit, k), min_and);
}
// Return the result
return min_and;
}
// Given array []arr
let arr = [ 2, 5, 3, 6, 11, 13 ];
// Given subarray size K
let k = 3;
let n = arr.length;
// Function call
document.write(minimumAND(arr, n, k));
</script>
Producción:
0
Complejidad de tiempo: O(n * B) donde n es el tamaño de la array y B es el bit de array entera de tamaño 32.
Espacio auxiliar: O(n)
- A continuación se muestra el programa para encontrar el subarreglo mínimo bit a bit XOR :
C++
// C++ program to find the subarray
/// with minimum XOR
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum XOR
// of the subarray of size K
void findMinXORSubarray(int arr[],
int n, int k)
{
// K must be smaller than
// or equal to n
if (n < k)
return;
// Initialize the beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for (int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for (int i = k; i < n; i++) {
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor) {
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
// Print the minimum XOR
cout << min_xor << "\n";
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
// Given subarray size K
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
findMinXORSubarray(arr, n, k);
return 0;
}
Java
// Java program to find the subarray
// with minimum XOR
class GFG{
// Function to find the minimum XOR
// of the subarray of size K
static void findMinXORSubarray(int arr[],
int n, int k)
{
// K must be smaller than
// or equal to n
if (n < k)
return;
// Initialize the beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for(int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for(int i = k; i < n; i++)
{
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor)
{
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
// Print the minimum XOR
System.out.println(min_xor);
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
// Given subarray size K
int k = 3;
int n = arr.length;
// Function call
findMinXORSubarray(arr, n, k);
}
}
// This code is contributed by rock_cool
Python3
# Python3 program to find the subarray # with minimum XOR # Function to find the minimum XOR # of the subarray of size K def findMinXORSubarray(arr, n, k): # K must be smaller than # or equal to n if (n < k): return; # Initialize the beginning # index of result res_index = 0; # Compute XOR sum of first # subarray of size K curr_xor = 0; for i in range(k): curr_xor ^= arr[i]; # Initialize minimum XOR # sum as current xor min_xor = curr_xor; # Traverse from (k+1)'th # element to n'th element for i in range(k, n): # XOR with current item # and first item of # previous subarray curr_xor ^= (arr[i] ^ arr[i - k]); # Update result if needed if (curr_xor < min_xor): min_xor = curr_xor; res_index = (i - k + 1); # Print the minimum XOR print(min_xor); # Driver Code if __name__ == '__main__': # Given array arr arr = [ 3, 7, 90, 20, 10, 50, 40 ]; # Given subarray size K k = 3; n = len(arr); # Function call findMinXORSubarray(arr, n, k); # This code is contributed by Amit Katiyar
C#
// C# program to find the subarray
// with minimum XOR
using System;
class GFG{
// Function to find the minimum XOR
// of the subarray of size K
static void findMinXORSubarray(int []arr,
int n, int k)
{
// K must be smaller than
// or equal to n
if (n < k)
return;
// Initialize the beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for(int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for(int i = k; i < n; i++)
{
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor)
{
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
// Print the minimum XOR
Console.WriteLine(min_xor);
}
// Driver Code
public static void Main(String[] args)
{
// Given array []arr
int []arr = { 3, 7, 90, 20, 10, 50, 40 };
// Given subarray size K
int k = 3;
int n = arr.Length;
// Function call
findMinXORSubarray(arr, n, k);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find the subarray
// with minimum XOR
// Function to find the minimum XOR
// of the subarray of size K
function findMinXORSubarray(arr, n, k)
{
// K must be smaller than
// or equal to n
if (n < k)
return;
// Initialize the beginning
// index of result
let res_index = 0;
// Compute XOR sum of first
// subarray of size K
let curr_xor = 0;
for(let i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
let min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for(let i = k; i < n; i++)
{
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor)
{
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
// Print the minimum XOR
document.write(min_xor);
}
// Driver code
// Given array arr[]
let arr = [ 3, 7, 90, 20, 10, 50, 40 ];
// Given subarray size K
let k = 3;
let n = arr.length;
// Function Call
findMinXORSubarray(arr, n, k);
// This code is contributed by divyeshrabadiya07
</script>
Producción:
16
Complejidad de tiempo: O(n * B) donde n es el tamaño de la array y B es el bit de array entera de tamaño 32.
Espacio auxiliar: O(n)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por Stream_Cipher y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA