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 \leq N \leq 10^3\)
\(1 \leq a_i \leq 10^6\)
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor