Dada una array de tamaño N y un número entero K . La tarea es particionar la array en K segmentos de modo que se maximice el AND bit a bit de la suma de segmentos individuales. Encuentre el valor máximo de AND bit a bit que se puede obtener.
Ejemplos:
Entrada: a[] = { 2, 5, 6, 9, 1, 3, 10, 12 }, K = 3
Salida: 8
Explicación:
El AND bit a bit máximo se puede obtener haciendo un corte en el 3er elemento y el 5to elemento (basado en 1 indexación)
(2+5+6)&(9+1)&(3+10+12) = 8
Entrada: a[] = { 1, 2, 7, 10, 23, 21, 6, 8, 7, 3 } , K = 2
Salida : 41
Explicación :
El AND bit a bit máximo se puede obtener haciendo un corte en el 5to elemento (indexación basada en 1)
(1+2+7+10+23)&(21+6+8+7+3 ) = 41
Enfoque:
Primero, intente responder una pregunta más simple: dado un número entero x y determine si es posible dividir la array dada en K segmentos de modo que el AND bit a bit de la suma de segmentos tenga todos los bits establecidos de x .
Denotemos la suma de elementos en el i- ésimo segmento por 
. Además, llamemos a un segmento bueno si tiene todos los bits establecidos de x . Está claro ahora que para un buen segmento i , AND ( , x )= x .
Además, todos los segmentos K deben ser buenospara obtener AND bit a bit de x . Ahora para verificar si podemos dividir la array en k buenos segmentos. Podemos usar programación dinámica aquí.
Sea dp[i][j]= true , denote que es posible dividir los primeros i elementos en j segmentos de modo que todos los j sean buenos segmentos, de lo contrario false .
La recurrencia para el dp anterior es:
dp[i][j] es 1, si para algún índice k<i, AND(suma de a[k+1]…a[i], x)=x y dp[k][j-1]=1 . De lo contrario, dp[i][j] es 0
Construya la tabla dp a partir de la parte más significativa de la posible respuesta con avidez.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find maximum possible AND
#include <bits/stdc++.h>
using namespace std;
// Function to check whether a k segment partition
// is possible such that bitwise AND is 'mask'
bool checkpossible(int mask, int* arr, int* prefix, int n,
int k)
{
// dp[i][j] stores whether it is possible to partition
// first i elements into j segments such that all j
// segments are 'good'
bool dp[n + 1][k + 1];
// Initialising dp
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
// Filling dp in bottom-up manner
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
// Finding a cut such that first l elements
// can be partitioned into j-1 'good' segments
// and arr[l+1]+...+arr[i] is a 'good' segment
for (int l = i - 1; l >= 0; --l) {
if (dp[l][j - 1] && (((prefix[i] - prefix[l])
& mask) == mask)) {
dp[i][j] = 1;
break;
}
}
}
}
return dp[n][k];
}
// Function to find maximum possible AND
int Partition(int arr[], int n, int k)
{
// Array to store prefix sums
int prefix[n+1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}
// Maximum no of bits in the possible answer
int LOGS = 20;
// This will store the final answer
int ans = 0;
// Constructing answer greedily selecting
// from the higher most bit
for (int i = LOGS; i >= 0; --i) {
// Checking if array can be partitioned
// such that the bitwise AND is ans|(1<<i)
if (checkpossible(ans | (1 << i), arr, prefix, n, k))
{
// if possible, update the answer
ans = ans | (1 << i);
}
}
// Return the final answer
return ans;
}
// Driver code
int main()
{
int arr[]={0, 1, 2, 7, 10, 23, 21, 6, 8, 7, 3}, k = 2;
// n = 11 , first element is zero
// to make array 1 based indexing. So, number of
// elements are 10
int n = sizeof(arr)/sizeof(arr[0])-1;
// Function call
cout << Partition(arr, n, k);
return 0;
}
Java
// Java program to find maximum possible AND
class GFG
{
// Function to check whether a k segment partition
// is possible such that bitwise AND is 'mask'
static boolean checkpossible(int mask, int arr[],
int prefix[], int n, int k)
{
int i,j;
// dp[i][j] stores whether it is possible to partition
// first i elements into j segments such that all j
// segments are 'good'
boolean dp[][] = new boolean[n + 1][k + 1];
// Initialising dp
for(i = 0; i < n + 1; i++)
{
for(j = 0; j < k + 1; j++)
{
dp[i][j] = false ;
}
}
dp[0][0] = true;
// Filling dp in bottom-up manner
for ( i = 1; i <= n; i++)
{
for (j = 1; j <= k; j++)
{
// Finding a cut such that first l elements
// can be partitioned into j-1 'good' segments
// and arr[l+1]+...+arr[i] is a 'good' segment
for (int l = i - 1; l >= 0; --l)
{
if (dp[l][j - 1] && (((prefix[i] - prefix[l])
& mask) == mask))
{
dp[i][j] = true;
break;
}
}
}
}
return dp[n][k];
}
// Function to find maximum possible AND
static int Partition(int arr[], int n, int k)
{
// Array to store prefix sums
int prefix[] = new int[n+1];
for (int i = 1; i <= n; i++)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Maximum no of bits in the possible answer
int LOGS = 20;
// This will store the final answer
int ans = 0;
// Constructing answer greedily selecting
// from the higher most bit
for (int i = LOGS; i >= 0; --i)
{
// Checking if array can be partitioned
// such that the bitwise AND is ans|(1<<i)
if (checkpossible(ans | (1 << i), arr, prefix, n, k))
{
// if possible, update the answer
ans = ans | (1 << i);
}
}
// Return the final answer
return ans;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {0, 1, 2, 7, 10, 23, 21, 6, 8, 7, 3}, k = 2;
// n = 11 , first element is zero
// to make array 1 based indexing. So, number of
// elements are 10
int n = arr.length - 1 ;
// Function call
System.out.println(Partition(arr, n, k));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find maximum possible AND # Function to check whether a k segment partition # is possible such that bitwise AND is 'mask' def checkpossible(mask,arr,prefix, n,k): # dp[i][j] stores whether it is possible to partition # first i elements into j segments such that all j # segments are 'good' dp=[[0 for i in range(k+1)] for i in range(n + 1)] # Initialising dp dp[0][0] = 1 # Filling dp in bottom-up manner for i in range(1, n+1): for j in range(1, k+1): # Finding a cut such that first l elements # can be partitioned into j-1 'good' segments # and arr[l+1]+...+arr[i] is a 'good' segment for l in range(i-1,-1,-1): if (dp[l][j - 1] and (((prefix[i] - prefix[l]) & mask) == mask)): dp[i][j] = 1 break return dp[n][k] # Function to find maximum possible AND def Partition(arr, n, k): # Array to store prefix sums prefix=[0 for i in range(n+1)] for i in range(1,n+1): prefix[i] = prefix[i - 1] + arr[i] # Maximum no of bits in the possible answer LOGS = 20 # This will store the final answer ans = 0 # Constructing answer greedily selecting # from the higher most bit for i in range(LOGS,-1,-1): # Checking if array can be partitioned # such that the bitwise AND is ans|(1<<i) if (checkpossible(ans | (1 << i), arr, prefix, n, k)): # if possible, update the answer ans = ans | (1 << i) # Return the final answer return ans # Driver code arr = [0, 1, 2, 7, 10, 23, 21, 6, 8, 7, 3] k = 2 # n = 11 , first element is zero # to make array 1 based indexing. So, number of # elements are 10 n = len(arr)-1 # Function call print(Partition(arr, n, k)) # This code is contributed by mohit kumar 29
C#
// C# program to find maximum possible AND
using System;
class GFG
{
// Function to check whether a
// k-segment partition is possible
// such that bitwise AND is 'mask'
static Boolean checkpossible(int mask, int []arr,
int []prefix,
int n, int k)
{
int i, j;
// dp[i,j] stores whether it is possible
// to partition first i elements into
// j-segments such that all j-segments are 'good'
Boolean[,] dp = new Boolean[n + 1, k + 1];
// Initialising dp
for(i = 0; i < n + 1; i++)
{
for(j = 0; j < k + 1; j++)
{
dp[i, j] = false;
}
}
dp[0, 0] = true;
// Filling dp in bottom-up manner
for ( i = 1; i <= n; i++)
{
for (j = 1; j <= k; j++)
{
// Finding a cut such that first l elements
// can be partitioned into j-1 'good' segments
// and arr[l+1]+...+arr[i] is a 'good' segment
for (int l = i - 1; l >= 0; --l)
{
if (dp[l, j - 1] &&
(((prefix[i] - prefix[l]) &
mask) == mask))
{
dp[i, j] = true;
break;
}
}
}
}
return dp[n, k];
}
// Function to find maximum possible AND
static int Partition(int []arr, int n, int k)
{
// Array to store prefix sums
int []prefix = new int[n + 1];
for (int i = 1; i <= n; i++)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Maximum no of bits in the possible answer
int LOGS = 20;
// This will store the final answer
int ans = 0;
// Constructing answer greedily selecting
// from the higher most bit
for (int i = LOGS; i >= 0; --i)
{
// Checking if array can be partitioned
// such that the bitwise AND is ans|(1<<i)
if (checkpossible(ans | (1 << i),
arr, prefix, n, k))
{
// if possible, update the answer
ans = ans | (1 << i);
}
}
// Return the final answer
return ans;
}
// Driver code
public static void Main (String[] args)
{
int []arr = {0, 1, 2, 7, 10, 23,
21, 6, 8, 7, 3};
int k = 2;
// n = 11 , first element is zero
// to make array 1 based indexing.
// So, number of elements are 10
int n = arr.Length - 1 ;
// Function call
Console.WriteLine(Partition(arr, n, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find maximum possible AND
// Function to check whether a k segment partition
// is possible such that bitwise AND is 'mask'
function checkpossible(mask, arr, prefix, n, k)
{
let i,j;
// dp[i][j] stores whether it is possible to partition
// first i elements into j segments such that all j
// segments are 'good'
let dp = new Array(n + 1);
// Initialising dp
for(i = 0; i < n + 1; i++)
{
dp[i] = new Array(k + 1);
for(j = 0; j < k + 1; j++)
{
dp[i][j] = false ;
}
}
dp[0][0] = true;
// Filling dp in bottom-up manner
for (i = 1; i <= n; i++)
{
for (j = 1; j <= k; j++)
{
// Finding a cut such that first l elements
// can be partitioned into j-1 'good' segments
// and arr[l+1]+...+arr[i] is a 'good' segment
for (let l = i - 1; l >= 0; --l)
{
if (dp[l][j - 1] && (((prefix[i] - prefix[l])
& mask) == mask))
{
dp[i][j] = true;
break;
}
}
}
}
return dp[n][k];
}
// Function to find maximum possible AND
function Partition(arr, n, k)
{
// Array to store prefix sums
let prefix = new Array(n+1);
prefix.fill(0);
for (let i = 1; i <= n; i++)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Maximum no of bits in the possible answer
let LOGS = 20;
// This will store the final answer
let ans = 0;
// Constructing answer greedily selecting
// from the higher most bit
for (let i = LOGS; i >= 0; --i)
{
// Checking if array can be partitioned
// such that the bitwise AND is ans|(1<<i)
if (checkpossible(ans | (1 << i), arr, prefix, n, k))
{
// if possible, update the answer
ans = ans | (1 << i);
}
}
// Return the final answer
return ans;
}
let arr = [0, 1, 2, 7, 10, 23, 21, 6, 8, 7, 3], k = 2;
// n = 11 , first element is zero
// to make array 1 based indexing. So, number of
// elements are 10
let n = arr.length - 1 ;
// Function call
document.write(Partition(arr, n, k));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
41
. Análisis de rendimiento:
Complejidad temporal: O(20*n 2 k) en el peor de los casos.
Complejidad espacial: O(n*k) en el peor de los casos.
Publicación traducida automáticamente
Artículo escrito por tech_mint0013 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA