Given an array of size N and an integer K. The task is to partition the array in K segments such that bitwise AND of individual segment sum is maximized. Find the maximum value of bitwise AND which can be obtained.
Examples:
Input : a[] = { 2, 5, 6, 9, 1, 3, 10, 12 }, K = 3
Output : 8
Explanation :
Maximum bitwise AND can be obtained by making cut at 3rd element and 5th element(1 based indexing)
(2+5+6)&(9+1)&(3+10+12) = 8
Input : a[] = { 1, 2, 7, 10, 23, 21, 6, 8, 7, 3 } , K = 2
Output : 41
Explanation:
Maximum bitwise AND can be obtained by making cut at 5th element(1 based indexing)
(1+2+7+10+23)&(21+6+8+7+3) = 41
Approach:
First, try to answer a simpler question: given an integer x and determine if it is possible to partition the given array into K segments such that the bitwise AND of sum of segments has all set bits of x?
Let’s denote the sum of elements in the ith segment by 
. Also, let’s call a segment good if has all set bits of x. It’s clear now that for a good segment i, AND(, x)=x.
Also, all K segments should be good for getting bitwise AND of x. Now to check whether we can partition the array into k good segments. We can use dynamic programming here.
Let dp[i][j]= true, denote that it is possible to partition first i elements into j segments such that all j are good segments otherwise false.
The recurrence for above dp is:
dp[i][j] is 1, if for some index k<i, AND(sum of a[k+1]…a[i], x)=x and dp[k][j-1]=1. Otherwise, dp[i][j] is 0
Build the dp table starting from the most significant bit of the possible answer greedily.
Below is the implementation of the above approach:
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 ANDint 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 codeint 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 ANDdef 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 codearr = [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 10n = len(arr)-1# Function callprint(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> |
Output:
41
.
Performance Analysis:
Time Complexity: O(20*n2k) in the worst case.
Space Complexity: O(n*k) in worst case.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
