Flipping easy and distributing fairly

Flipping binary numbers

Our first task this week is to take a positive integer, render it in binary, swap the zeroes for ones and vice versa, and output the result in decimal.

It's tempting to use the Perl bitwise not operator (~) to flip the bits, but inspection of the examples shows that's not quite what's wanted. The reason is that while we normally express 4, for example, as 100 in binary, the computer consider it to be 0000000000000100. Applying the not operator to that gives us 1111111111111011, which isn't the desired answer.

Now there are various ways around that, but note that the supplied number will always start with a 1 in its simple binary representation, so its flipped value will start with 0. And in its 16 (or whatever) bit representation, that will be preceded by a lot of 1s. So as it's just a string, we can safely just strip off all the leading 1s using s|^1+||, and the algorithm boils down to just two lines:

$flip = sprintf('%b', ~ $test);    # render 'not' the test in binary
$flip =~ s|^1+||;                  # strip off any leading 1s

Making an even distribution

For this task we are given an ordered list of integers and asked to make 'moves' until all the members of the list are equal. A move comprises subtracting 1 from any cell in the list and adding it to an immediately neighbouring cell.

We are asked to return the number of moves requires, or -1 if the task cannot be achieved.

The first thing to note is that if there are c cells and the sum of their contents is s, then an answer can only be possible if s is an integer multiple of c.  If it is, the cells will all end up containing s/c. So we can immediately return -1 if s is not a multiple of c.

It is clear then that it is always possible to even out the distribution using 'moves' as described above.

The algorithm I have used goes as follows.

First check that the input meets the s/c criterion, and if not, return -1.

Start at cell 0 and work along to the second-last cell (because if we get all those right then the last cell must be right too).

We know what the target value in each cell is - it's s/c.  So if the cell we are looking at:

• contains more than the target, we successively reduce it by 1 and increment  the following cell by 1 until the cell we are looking at contains the target value
• contains less than the target, we successively reduce it by 1 and increment  the following cell by 1 until the cell we are looking at contains the target value
• contains exactly the target, we do nothing

We count the moves as we go, and the statement of the task only requires us to output that number. So that's it.

However, there is slight wrinkle. Although that algorithm gives numbers of moves which agree with the examples, it is the case that some of the moves may temporarily leave a cell containing a negative number.  For example, for Mohammad's first example it gives this:

Input:  (1, 0, 5)
Output: 4

   Move #1: 2, -1, 5
   Move #2: 2, 0, 4
   Move #3: 2, 1, 3
   Move #4: 2, 2, 2

The rules don't say that this is not allowed, so I am boldly claiming that it is valid.

I also believe, though won't show the proof here, that:

• this algorithm always comes up with the minimum number of moves,
• the moves can always be rearranged such that no cell goes negative, and
• there are multiple alternative sets of a greater number of moves to get to the desired equal distribution.