Problem:

Given a decimal number, find the next bigger decimal number having same numbers of 1's and 0's in binary format as original number. like 11011 and 11110 have same number of 1's and 0's.

**Input Format:**

t=number of test cases

followed by t lines having a decimal number

followed by t lines having a decimal number

**Output Format:**

next big decimal number for each input in new line

**Constraints:**

none

Sample Input

2

21

44

21

44

Sample Output:

22

49

22

49

Explanations:

for case 2, 44 in binary is 101100 have 3 1's and 3 0's, next bigger number with same bits is 110001 ie 49.

for case 2, 44 in binary is 101100 have 3 1's and 3 0's, next bigger number with same bits is 110001 ie 49.

Solution:

while($n>0)

{

$a=<STDIN>;

$b=sprintf("%b",$a);

$b='0'.$b;

$b=~s/(.*)01(.*)/$1 10 $2/;

$q=join '',sort split('',$2);

$b=~s{(.*)$2}{$1$q};

$b=~s/\s//g;

$x=oct("0b".$b);

push(@o,$x);

$n--;

}

foreach(@o)

{

print"$_\n";

}

Tips:

Next bigger number is formed by finding first 01 from the right and replacing it by 10 , then arranging remaining characters on right to make it minimum, like 1010 to 0011.

## No comments:

## Post a Comment