Let's solve a bit different problem first:
What minimum min number should be add to value to ensure 1 in kth position (zero based)?
We have two cases here:
if value has 1 at k position we add 0 (do nothing);
if value has 0 at k position we can add
min = 100...000000000 - (value & 11.....11111)
<- k zeroes -> <- k ones ->
Code (C#)
private static long AddToEnsureOne(long value, int position) {
if ((value & (1L << position)) != 0)
return 0;
long shift = 1L << (position);
return shift - (value & (shift - 1));
}
Demo: if we have 3 and we want 1 at 2nd position
0b011
^
we want 1 here
we should add
0b100 - (0b011 & 0b11) == 4 - 3 == 1
let's add: 3 + 1 == 4 == 0b100 which has 1 at 2nd position
Now we can scan all 32 positions (if integer is good old 32 bit integer int); C# code:
private static long MinToAdd(IEnumerable<int> items) {
long best = 0;
for (int i = 0; i < 32; ++i) {
long sum = 0;
foreach (int item in items)
sum += AddToEnsureOne(unchecked((uint)item), i); // uint - get rid of sign
if (i == 0 || sum < best)
best = sum;
}
return best;
}
One can improve the solution looping not for 32 positions but for the leftmost 1 of the maximum item. Here we have 4 as the maximum, which is 0b100, the leftmost 1 is in the 2 position; thus for (int i = 0; i <= 2; ++i) will be enough in the context
Simple test:
Console.Write(MinToAdd(new int[] { 4, 4, 3, 2}));
Outcome:
3
