Problem Statement
Let S be a set containing k non-negative integers: { S[0], ..., S[k-1] }.
We define OR(S) to be the bitwise "or" of all elements of S.
Formally:
OR(S) = S[0] or S[1] or ... or S[k-1].
For consistency, if S is the empty set, then OR(S) is defined to be 0.
A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values.
You are given a int[] A that describes a set of integers. Your goal is to select a subset B of the set described by A. The subset B has to be independent with respect to OR, and the sum of its elements has to be as large as possible. Return the largest possible sum of elements of the set B.
A set T is called "independent with respect to OR" if no two subsets of T produce the same value when OR is applied to them. Formally, T should have the following property: | { OR(S) : S is a subset of T } | = 2^|T|. In words: the set of all values OR(S), where S is a subset of T, contains exactly (2 to the size of T) distinct values.
You are given a int[] A that describes a set of integers. Your goal is to select a subset B of the set described by A. The subset B has to be independent with respect to OR, and the sum of its elements has to be as large as possible. Return the largest possible sum of elements of the set B.
Definition
- Class:
- IndependentOfOR
- Method:
- maxSum
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int maxSum(int[] A)
- (be sure your method is public)
Constraints
- A will contain between 1 and 50 elements, inclusive.
- All elements of A will be pairwise distinct.
- Each element in A will be between 1 and 1,000,000, inclusive.
Examples
{2, 3}Returns: 3
The optimal solution is: {3}. Note that {2, 3} is not a valid solution, since |OR({2, 3})| = |{0, 2, 3}| = 3 < 2^2 = 4.{1, 2, 3, 4, 5, 6}Returns: 11
This time the optimal solution is {5, 6}.{2, 3, 5, 7, 11, 13, 17, 19}Returns: 41
{8, 9, 13, 45, 47, 111, 127}Returns: 127
{5, 8, 55, 58, 85, 88, 555, 558, 585, 588, 855, 858, 885, 888}Returns: 2919
{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288}Returns: 1048575
Back to all problems