CareerCup

Try to find the last occurrence of the pattern "01" in the binary representation of the number.
Set that 01 to 10, and put all 1's after that position to the end.
e.g.
n=10111 01110
the last occurrence of 01 is of index 6.
the algorithm gives m=10111 10011.

Count the number of Bits that are set in the given number
This can be done in O(no of bits that are set) time
Now the number can be from left to right all 1 set and then 0

Eg
110010
Bits set : 3
new number 111000

ftfish's approach seems correct.
@ibnipun10: your ans is wrong. it'd be 110100.

@buried: Can you please explain as to why the ans is wrong?

<pre lang="java" line="1" title="CodeMonkey18842" class="run-this">class NextBinary {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int k = 12;
System.out.printf("Input Number:%2d", k);
System.out.printf(" Binary Format:%3s", Integer.toString(k, 2));
System.out.println();
int n = nextBinary(k);
System.out.print("Output Number:" + n);
System.out.printf(" Binary Format:%3s", Integer.toString(n, 2));
}

private static int nextBinary(int z) {
// TODO Auto-generated method stub
int i = 0;
int ones = 0;
while ((z & 1 << i) == 0)
i++;
z = z & ~(1 << i);
i++;
while ((z & 1 << i) > 0) {
i++;
ones++;
}
z = z | (1 << i);
i--;
while (i >= ones) {
z = z & ~(1 << i);
i--;
}
while (i >= 0) {
z = z | (1 << i);
i--;
}
return z;

}

}
</pre><pre title="CodeMonkey18842" input="yes">1
2
10
42
11

</pre>

can't we just multiply the number by 2 ???

int nextGreaterNumWithSameNumOfOnes(unsigned int num)
{
unsigned int numOfZeros = 0 , numOfOnes = 0;

if ( num == 0)
return 0;

// count num of zeros
while(num%2 == 0)
{
numOfZeros++;
num = num>>1;
printf("num of 0's %d \n",numOfZeros);
}

//count num of 1's
while(num && (num%2 == 1))
{
numOfOnes++;
num = num>>1;
printf("num of 1's %d \n",numOfOnes);

}

//flip the bit .. LSB's 0
num = num + 1;

//shift 1
num = num << 1; // move zero into LSB
numOfOnes--; // remove 1 bit from original binary form

while(numOfOnes)
{
num = num << 1;
num = num+1;
numOfOnes--;
}

while(numOfZeros)
{
num = num<<1;
numOfZeros--;
}

printf("next greater num is %d \n",num);

return num;

}

return n*2

multiplying with 2 is incorrect:
for n=6 i.e 110 n*2= 12 i.e.. 1100
but ans should be 1001

ftfish is correct:
find last occurence of "01" replace it with "10" then move all 1' to the end.

multiplying with 2 is incorrect:
for n=6 i.e 110 n*2= 12 i.e.. 1100
but ans should be 1001

ftfish is correct:
find last occurence of "01" replace it with "10" then move all 1' to the end.