Bitwise anding interesting question. Simple yet not so simple.

Bitwise anding interesting question. Simple yet not so simple.

Given an array AA of nn integers, the elements are shuffled to form an array BB.

Let the array BB be b0,b1,...bn−1b0,b1,...bn−1.

We define fi=b0fi=b0&b1b1&...bi...bi.

We need to find the minimum possible value of ∑n−1i=0fi∑i=0n−1fi.

Constraints:
1 <= n <= 1000
0 <= bibi <= 1015

Sample input: 10, 1, 21, 1

Answer: 1

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.

Note:
Sorting in decreasing won't work. Eg: 1, 1, 2 sorting -> 1, 1, 2 optimal -> 1, 2, 1