Recently I had experience with solving some teasers from codility.com site, here is one of problems and how I solved it.

So the task is about converting integers into bytes representation, or more simply a number written in base -2. The formula is B[i]*(ā2)i for i = [0..Nā1] where B is array of bytes and N is length of this array.

For example we have following array [1,0,0,1,1], then to find out actual integer we have to:

1 * (-2)^0 = 1 0 * (-2)^1 = 0 0 * (-2)^2 = 0 1 * (-2)^3 = -8 1 * (-2)^4 = 16 integer = 1 + 0 + 0 - 8 + 16 = 9

So the actual PHP code to get integer from base -2 is:

function int_of_base_neg2($a) { $count = count($a); $result = 0; for($i = 0; $i < $count; $i ++) { $result += $a[$i] * pow(-2, $i); } return $result; }

This is quite simple and straightforward. The complex part here is how to do this in opposite way. My solution is not fully written by me, and I’m not sure if it works correct in any situation, but here it is:

function base_neg2_of_int($n) { $result = []; while($n !== 0) { $remainder = (int) ($n % -2); $n = (int) ($n / - 2); if ($remainder < 0) { $remainder += 2; $n += 1; } $result[] = $remainder; } return $result; }

Finally, my actual task was to convert given array to integer, then turn this integer to negative and convert it back to base -2 bytes array, and here is how to do this:

function solution($A) { $int = int_of_base_neg2($A); $neg_int = - $int; $result = base_neg2_of_int($neg_int); return $result; }

And this is it. I have to say I’m not very good in this algorithms. That’s maybe what people study in universities for programming, but in real work, especially in Web development I never used any of this kind of algorithms I encountered at tests on codility.com or hakerrank.com.

You can play with this code here: http://ideone.com/Li6B8V