Author: Prateek Gupta
Tester: Praveen Dhinwa
Editorialist: Prateek Gupta
Given an array of length N, you need to select a subsequence from an array and remove the integers contained it. The cost incurred to remove a subsequence is the Bitwise OR of all the elements in that particular subsequence. This operation can be performed any number of times. The final goal is to minimize the total cost after the array becomes empty. Total cost is the sum of costs of all operations.
The problem can indeed be solved by simple observation.
It is first important to understand how the Bitwise OR operation actually works. A bitwise OR for two integers takes their corresponding bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1.
In order to incur the minimum cost, it is necessary to select a complete array as a subsequence so that the total cost will be the Bitwise OR of all the integers in the array. But, why this will give you the minimum cost?
Consider a number that has some set bits in it’s binary representation. There may be another number in the array who might have set bits in the same position. In case, you do not take these numbers in a single operation, you will end up adding the value contributed by that common set bits twice. However, if you take them as a part of the same subsequence, you do a Bitwise OR and the value contribution for common set bit just get added up only once to the final cost.
Let us look at the pseudo code below.
ans = 0 for each integer in array ans = (ans OR integer) print(ans)
Overall complexity of the solution remains O(N).
Author’s solution can be found here.
Tester’s solution can be found here.