Question

Triology | CodeNation | Coding | OA | SDE | Set-20

Answer 1

You are given an array of size n and an integer k, you have to partition the array into k contiguous subarrays such that the sum of bitwise OR of all the subarrays is maximised. Each element should belong to a partition.

eg -> A = [1, 2, 3, 4], k = 2 1st way: [1], [2, 3, 4] -> (1) + (2 | 3 | 4) = 8 2nd way: [1, 2], [3, 4] -> (1 | 2) + (3 | 4) = 10 3rd way: [1, 2, 3], [4] -> (1 | 2 | 3) + 4 = 7 Hence, the answer is 10.

N = 10^3

This question came up in Trilogy Innovations OA round, Well, I arrived to a simple DP solution that was O(n^3), How can this be optimised further?