Particionar la array en K segmentos de modo que se maximice el AND bit a bit de la suma de segmentos individuales

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:
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  S\subíndice de texto{i}     . Además, llamemos a un segmento bueno si  S\subíndice de texto{i}     tiene todos los bits establecidos de x . Está claro ahora que para un buen segmento i , AND ( S\subíndice de texto{i}     , 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *