## 8 November 2014

### Quiz 44: Find the next bigger number with same bits

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

Output Format:
next big decimal number for each input in new line

Constraints:
none

Sample Input
2
21
44

Sample Output:
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.

Solution:

\$n=<STDIN>;
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.