Bitwise anding interesting question. Simple yet not so simple.

Revision en3, by abhaypatil2000, 2021-11-13 01:15:07

Given an array $$$A$$$ of $$$n$$$ integers, the elements are shuffled to form an array $$$B$$$.

Let the array $$$B$$$ be $$$b_0,b_1,...b_{n-1}$$$.

We define $$$f_i = b_0$$$&$$$b_1$$$&$$$... b_i$$$.

We need to find the minimum possible value of $$$\sum_{i=0}^{n-1} f_i$$$.

Constraints:
1 <= n <= 1000
0 <= $$$b_i$$$ <= 1015

Here is my solution, which just kinda solves it, but I am not satisfied

There are basically 2 processes in the solution. Each process returns an answer. Do the first process, obtain the first answer. Do the second process, and obtain another answer. And return the min of both these answers.

Process 1:
Find the min element, and swap it with the 0th element, make it the prefix_and. Now loop on i from 1 to n-1, and find the element which gives the smallest and with pref_and, and swap that element with ith element, and now make pref_and &= ith element. Return the pref_and as the answer.

Process 2:
Consider all the pairs of 2 elements in the array, and find that pair which results in the smallest and. In this pair, swap the smaller element with 0th element and the other with the 1st element. Now loop on i from 2 to n-1, and continue as in Process 1. Return the pref_and.

The thing is that I don't know why this works. I.e., I don't have a formal proof, or a convincing enough proof. I just tried Process 1, and half the cases passed, and when I changed my solution to Process 2, the other half test cases passed.

So I just merged both these solutions, and got an AC. So not sure why this works.

Tags bitwise operators, array, minimization

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English abhaypatil2000 2021-11-13 01:19:34 145
en3 English abhaypatil2000 2021-11-13 01:15:07 1226
en2 English abhaypatil2000 2021-11-12 23:35:13 67 Tiny change: 'nstraints:\n1 <= n <= 1000\n0 <= $b_' -> 'nstraints: \n1 <= n <= 1000 \n0 <= $b_'
en1 English abhaypatil2000 2021-11-12 23:33:44 322 Initial revision (published)