Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,479 views
in Online Assessments by Expert (35,210 points)
edited by | 1,479 views

1 Answer

0 like 0 dislike
Best answer
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?
by Expert (35,210 points)
selected by