You are given an array of N numbers, and you are asked to minimize the total "OR cost" incurred when reducing the array to a single number. To achieve this, you need to follow these steps:
- Select any two numbers P and Q from the array. The cost of selecting these two numbers is ((P + Q) + (P | Q) - (P & Q)), where "|" denotes the bitwise OR operator, and "&" denotes the bitwise AND operator.
-
Choose one of the two numbers you selected in the previous step and remove it from the array. Concatenate the remaining numbers.
-
Repeat the above two steps until the array is reduced to a single number.
The "OR cost" is defined as the bitwise OR of all the costs incurred in reducing the array to a single number.
Input Format :
An integer N denoting the size of the array
N integers denoting the elements of the array
Output Format :
Print one integer, the minimum OR cost
Constraints :
1≤N≤103
1≤ai≤106
Sure, here's a possible rephrased version of the explanation:
Consider the following example array: [1, 5, 2, 3]. To minimize the total "OR cost," we can follow these steps:
-
Select 1 and 5. Remove 5 from the array, and concatenate the remaining numbers [1, 2, 3]. The cost incurred is ((1 + 5) + (1 | 5) - (1 & 5)) = 10.
-
Select 1 and 2. Remove 2 from the array, and concatenate the remaining numbers [1, 3]. The cost incurred is ((1 + 2) + (1 | 2) - (1 & 2)) = 6.
-
Select 1 and 3. Remove 1 from the array, and concatenate the remaining numbers [3]. The cost incurred is ((1 + 3) + (1 | 3) - (1 & 3)) = 6.
Thus, the total "OR cost" is the bitwise OR of the individual costs incurred, which is (10|6|6) = 14. It can be shown that we can never achieve a total cost less than 14 for this particular array.
