partition of array into k contiguous subarrays such that bitwise AND of sum of each subarray is maximum

Question

An array of size n (n<=50) containing positive integers is given. You have to divide the array into k contiguous subarrays in such a way that the bitwise AND of all subarray sums is maximized.

For example with array=[30,15,26,16,21] and k=3, consider all partitions:

• (30) & (15) & (26+16+21) = 14
• (30) & (15+26) & (16+21) = 0
• (30) & (15+26+16) & (21) = 16
• (30+15) & (26+16) & (21) = 0
• (30+15) & (26) & (16+21) = 0
• (30+15+26) & (16) & (21) = 0

Maximum of all is 16, so the answer for this array is 16.

I am not getting any idea other than brute force. Please help.

static void findMaxAND(int[] arr,int k){
        if (k>arr.length){
            System.out.println(0);
            return;
        }
        int n=arr.length;
        int[] parSum=new int[n];
        parSum[0]=arr[0];
        for (int i=1;i<n;i++){
            parSum[i]+=parSum[i-1]+arr[i];
        }

        int upperSum=parSum[n-1]/k;
        int upperBit=(int)Math.floor((Math.log10(upperSum)/Math.log10(2)));

        partitions=new ArrayList<>();
        while (true){
            int min=(int)Math.pow(2,upperBit);

            check(arr,min,-1,new ArrayList<>(),1,k);
            if (!partitions.isEmpty()){
                int maxAND=Integer.MIN_VALUE;
                for (List<Integer> partiton:partitions){
                    partiton.add(n-1);
                    int innerAND=parSum[partiton.get(0)];
                    for (int i=1;i<partiton.size();i++){
                        innerAND&=(parSum[partiton.get(i)]-parSum[partiton.get(i-1)]);
                    }

                    maxAND=Math.max(maxAND,innerAND);
                }
                System.out.println(maxAND);
                break;
            }

            upperBit--;
        }
    }

    private static List<List<Integer>> partitions;

    static void check(int[] arr,int min,int lastIdx,List<Integer> idxs,int currPar,int k){
        int sum=0;
        if (currPar==k){
            if (lastIdx>=arr.length-1){
                return;
            }
            int i=lastIdx+1;
            while (i<arr.length){
                sum+=arr[i];
                i++;
            }
            if ((sum&min)!=0){
                partitions.add(new ArrayList<>(idxs));
            }
        }
        if (currPar>k||lastIdx>=(arr.length-1)){
            return;
        }

        sum=0;
        for (int i=lastIdx+1;i<arr.length;i++){
            sum+=arr[i];
            if ((sum&min)!=0){
                idxs.add(i);
                check(arr,min,i,idxs,currPar+1,k);
                idxs.remove(idxs.size()-1);
            }
        }
    }

It is working but time complexity is too bad.

Answer 1

Below is a non-recursive dynamic-programming solution (in JavaScript, though it should be very straightforward to port it to Java). It works in a similar way to what user3386109's comment and גלעד ברקן's answer suggest, though I'm not sure if it's exactly the same. (It performed much better than גלעד ברקן's answer when I tested it, but that might be due to minor implementation differences rather than meaningful conceptual differences.)

Its overall complexity is worst-case O(n²kb) time and O(nk) extra space, where b is the number of bits to try — I just hardcoded it to 31 below, which performed just fine in practice, though you can optimize it if desired by ruling out larger numbers. (N.B. I'm assuming here that additions and bitwise-ANDs are O(1). If we have to support really large numbers, then the actual worst-case time complexity will be O(n²kb²).)

See code comments for details.

function f(array, numSegments) {
  const n = array.length;
  const maxBit = (1 << 30); // note: can improve if desired

  if (numSegments > n) {
    throw 'Too many segments.';
  }

  /* prefixSums[i] will be the sum of array[0..(i-1)], so that
   * the sum of array[i..j] will be prefixSums[j+1]-prefixSums[i].
   * This is a small optimization and code simplification, but the
   * same asymptotic complexity is possible without it.
   */
  const prefixSums = [];
  prefixSums[0] = 0;
  for (let i = 1; i <= n; ++i) {
    prefixSums.push(prefixSums[i-1] + array[i-1]);
  }

  /* bestKnownBitmask will be the result -- the best bitmask that we
   * could achieve. It will grow by one bit at a time; for example,
   * if the correct answer is binary 1011, then bestKnownBitmask will
   * start out as 0000, then later become 1000, then later 1010, and
   * finally 1011.
   */
  let bestKnownBitmask = 0;

  /* startIndices[seg] will be a list of start-indices where
   * it's possible to divide the range from such a start-index to
   * the end of the array into 'seg' segments whose sums all satisfy
   * a given bitmask condition.
   *
   * In particular, startIndices[0] will always be [n], because the
   * only way to get zero segments is to have zero elements left; and
   * startIndices[numSegments][0] will always be 0, because we only
   * keep a bitmask condition if we successfully found a way to
   * partition the entire array (0..(n-1)) into 'numSegments' segments
   * whose sums all satisfied it.
   */
  let startIndices = [];
  startIndices.push([n]);
  for (let seg = 1; seg <= numSegments; ++seg) {
    startIndices.push([]);
    for (let i = numSegments - seg; i <= n - seg; ++i) {
      startIndices[seg].push(i);
    }
  }

  for (let currBit = maxBit; currBit > 0; currBit >>= 1) {
    const bitmaskToTry = (bestKnownBitmask | currBit);

    const tmpStartIndices = startIndices.map(row => []); // empty copy
    tmpStartIndices[0].push(n);

    for (let seg = 1; seg <= numSegments; ++seg) {
      for (const startIndex of startIndices[seg]) {
        for (const nextIndex of tmpStartIndices[seg-1]) {
          if (nextIndex <= startIndex) {
            continue;
          }
          const segmentSum = prefixSums[nextIndex] - prefixSums[startIndex];
          if ((segmentSum & bitmaskToTry) === bitmaskToTry) {
            tmpStartIndices[seg].push(startIndex);
            break;
          }
        }
      }
    }

    if (tmpStartIndices[numSegments].length > 0
        && tmpStartIndices[numSegments][0] === 0) {
      // success!
      bestKnownBitmask = bitmaskToTry;
      startIndices = tmpStartIndices;
    }
  }

  return bestKnownBitmask;
}

function runFunctionAndLogResult(array, numSegments) {
  let startTime = performance.now();
  let result = f(array, numSegments);
  let endTime = performance.now();
  console.log(
    'array = [' + array.join(', ') + ']\n' +
    'k = ' + numSegments + '\n' +
    'result = ' + result + '\n' +
    'time = ' + (endTime - startTime) + ' ms'
  );
}

runFunctionAndLogResult(
  [ 25, 40, 45, 69, 26, 13, 49, 49, 84, 67, 30, 22, 43, 82, 2, 95, 96, 63, 78, 26, 95, 57, 80, 8, 85, 23, 64, 85, 12, 66, 74, 69, 9, 35, 69, 89, 34, 2, 60, 91, 79, 99, 64, 57, 52, 56, 89, 20, 8, 85 ],
  12
);

Answer 2

Here's an idea with a reference to user3386109's suggestion in the comments, although instead of having the possible AND of a subarray as a parameter, we have the current highest set bit.

Given a prefix with highest set bit b, we'd like to return all AND combinations with suffixes that have b set. If there are none, we can't use this bit so try a lower one. Note that the values generated from all possible partitions that have the highest fixed bit set will necessarily include the best overall answer among them.

The recursion below has left_index, right_index, current_k, bth_bit_set as parameters (and search space) and a list of possible values as a result. We apply memoization both to a single call and to the aggregation of calls for a range of calls with a fixed left and varying right index (seems like brute force, no?).

JavaScript code follows (not sure if this consistently works :) Unless I made some mistake, or it's really hard to get degenerate data, it seems like fixing the high bit, as user3386109 suggested, prunes the search space substantially.

function f(arr, K){
  let str = `Array:\n${ arr.join('\n') }` + 
            `\n\nK: ${ K }\n\n`

  let hash = {
    f: {},
    f_range: {}
  }

  function g(l, r, k, b, A, K){
    // Out of bounds
    if (r > A.length - 1 || k > K || b < 0)
      return []

    if (hash.f.hasOwnProperty([l, r, k, b]))
      return hash.f[[l, r, k, b]]
      
    let s = pfxs[r] - pfxs[l-1]
    
    // This sum does not have
    // the bth bit set
    if (!(s & (1 << b)))
      return hash.f[[l, r, k, b]] = []
      
    if (r == A.length - 1){
      if (k < K)
        return hash.f[[l, r, k, b]] = []
      else
        return hash.f[[l, r, k, b]] = [s]
    }
    
    if (k == K){
      if (r == A.length - 1)
        return hash.f[[l, r, k, b]] = s & (1 << b) ? [s] : []
      else
        return hash.f[[l, r, k, b]] = g(l, r + 1, k, b, A, K)
    }
    
    // Possible suffixes
    let sfxs = []
    // Number of parts outstanding
    let ks = K - k
    // Upper bound for next part
    let ub = A.length - ks + 1
    
    if (hash.f_range.hasOwnProperty([r + 1, ub, k + 1, b])){
      sfxs = hash.f_range[[r + 1, ub, k + 1, b]]

    } else {
      for (let rr=r+1; rr<ub; rr++)
        sfxs = sfxs.concat(
          g(r + 1, rr, k + 1, b, A, K)
        )
      hash.f_range[[r + 1, ub, k + 1, b]] = sfxs
    }
        
    // We have a possible solution
    if (sfxs.length){
      result = []
      
      for (let sfx of sfxs)
        result.push(s & sfx)
      
      return hash.f[[l, r, k, b]] = result
    
    } else {
      return []
    }
  }

  // Array's prefix sums
  let pfxs = [arr[0]]
  for (let i=1; i<arr.length; i++)
    pfxs[i] = arr[i] + pfxs[i - 1]
  pfxs[-1] = 0

  let highBit = -1

  let maxNum = arr.reduce((acc, x) => acc + x, 0)
  while (maxNum){
    highBit++
    maxNum >>= 1
  }

  str += `\nhigh bit: ${ highBit }`

  let best = 0

  for (let b=highBit; b>=0; b--){
    for (let r=0; r<arr.length-K+1; r++){
      let result = g(0, r, 1, b, arr, K)
      //str += `\n${ JSON.stringify(result) }`
      if (result.length)
        best = Math.max(best, Math.max.apply(null, result))
    }
    if (best)
      break
  }
  console.log(str + '\n')
  return best
}

let arr = [30, 15, 26, 16, 21]
let K = 3
console.log(`result: ${ f(arr, K) }\n\n`)

let rand_arr = []
let rand_len = Math.ceil(Math.random() * 49)
for (let i=0; i<rand_len; i++){
  let rand_exp = ~~(Math.random() * 30)
  rand_arr[i] = Math.ceil(Math.random() * (1 << rand_exp))
}
let rand_k = Math.ceil(Math.random() * rand_len)

console.log(`result: ${ f(rand_arr, rand_k) }\n\n`)

const ex = [ 25, 40, 45, 69, 26, 13, 49, 49, 84, 67, 30, 22, 43, 82, 2, 95, 96, 63, 78, 26, 95, 57, 80, 8, 85, 23, 64, 85, 12, 66, 74, 69, 9, 35, 69, 89, 34, 2, 60, 91, 79, 99, 64, 57, 52, 56, 89, 20, 8, 85 ]

console.log(`result: ${ f(ex, 12) }`)

Sample output

Array:
9598
15283236
121703215
80
25601067
761
7071
428732360
238244
2
176
116076
4
3517
491766404
5619908
39459923
330411
8
38

K: 5


high bit: 30

result: 4259840

More sample output:

Array:
3853
7668
77853
1
3
6652
166
2
5
15323609
17252
3422
1
122913
8
17
89263
21934
332522269
44900
1014
2503905
449429594
4190
3
166469508
1
898071

K: 3


high bit: 29
result: 12713984