Gray Code Generation - n-bit Gray Codes

The question is asked by hackerrank and i got the solution, but there is a problem in the solution at last test cases.

The question is below.

1 <= $n <= 65

Following is 1-bit sequence (n = 1)

0 1

Output

1

Following is 2-bit sequence (n = 2)

00 01 11 10

Output

11 10

Following is 3-bit sequence (n = 3)

000 001 011 010 110 111 101 100

Output

111 101 100

Following is 4-bit sequence (n = 4)

 0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 
  1110 1010 1011 1001 1000

Output

1010 1011 1001 1000

Solution Example

following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.

• L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes)
• L2 = {10, 11, 01, 00} (Reverse of L1)
• Prefix all entries of L1 with ‘0’, L1 becomes {000, 001, 011, 010}
• Prefix all entries of L2 with ‘1’, L2 becomes {110, 111, 101, 100}
• Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}

The First Solution is given below.(based on solution example above)

but the given solution below will not work after 22,23 numbers. The memory allocation error occurred.

<?php

$input = 2;

$list_array = ["0","1"];
$reverse_array = array_reverse($list_array);

for($i = 1; $i < $input; $i++ )
{
    for($j = 0; $j < sizeof($list_array); $j++)
    {
        $list_array[$j] = "0".$list_array[$j];
    }

    for($k = 0; $k < sizeof($reverse_array); $k++)
    {
        $reverse_array[$k] = "1".$reverse_array[$k];
    }

    $list_array = array_merge($list_array,$reverse_array);
    $reverse_array = array_reverse($list_array);
}

for($l = sizeof($list_array) - $input; $l < sizeof($list_array); $l++)  
{
    print_r($list_array[$l]);
    echo "<br />";
}

?>

The second solution is given below

This solution will work till 63. After 63 this will show timeout error.

This will work till 63 when the 64 bit php running on 64 bit os. if it is 32 bit php running on 64 bit os, it will not work after 31.

<?php

    $n = 59;

    $intial = pow(2, $n) - $n;

    $length = pow(2, $n) - 1;

    for($i= $intial; $i <= $length; $i++)
    {
        $decimal = ($i >> 1) ^ $i;
        print_r(decbin($decimal));
        echo "<br />";
    }
?>

please help me for finding this solution.

question: how to solve above including $n = 64 and $n = 65

reference: https://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/

This should work for you:

<?php

print_r( getResult( 4 ) );

function getResult ( $n ) {
    $result = [];
    for ( $i = 0; $i < $n; $i++ ) {
        $result[] = arr_xor(
          str_split( str_pad( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), $n, '1', STR_PAD_LEFT ) ),
          str_split( '0' . str_pad( substr( str_pad( strtr( decbin($n - $i - 1), '01', '10' ), (int)ceil(log($n - $i - 1, 2)), '0', STR_PAD_LEFT ), -1-(int)ceil(log($n - $i - 1, 2)), -1), $n - 1, '1', STR_PAD_LEFT ) )
        );
    }
    return $result;
}

function arr_xor( $a, $b ) {
    $result = [];
    for ( $i = 0; $i < count( $a ); $i++ )
        $result[] = (int)$a[$i] ^ (int)$b[$i];
    return implode( '', $result );
}

It just uses the formula from your second solution (($i >> 1) ^ $i), but since you can't use that for integers greater than PHP_INT_MAX, it uses an array with each element representing one bit. It's not the most efficient solution, but can easily go beyond 65. $n = 1000 seems to be no problem.