Binary representation of next greater number with same number of 1’s and 0’s in C Program?

Suppose we have one binary number, that is representation of a number n. We have to find binary representation of a number which is smallest but larger than n, and it also has same number of 0s and 1s. So if the number is 1011 (11 in decimal), then the output will be 1101 (13). This problem can be found using the next-permutation calculation. Let us see the algorithm to get the idea.

Algorithm

nextBin(bin) −

Begin    len := length of the bin    for i in range len-2, down to 1, do       if bin[i] is 0 and bin[i+1] = 1, then          exchange the bin[i] and bin[i+1]          break       end if    done    if i = 0, then there is no change, return    otherwise j:= i + 2, k := len – 1    while j < k, do       if bin[j] is 1 and bin[k] is 0, then          exchange bin[j] and bin[k]          increase j and k by 1       else if bin[i] is 0, then          break       else          increase j by 1       end if    done    return bin End

Example

#include <iostream> using namespace std; string nextBinary(string bin) {    int len = bin.size();    int i;    for (int i=len-2; i>=1; i--) {       if (bin[i] == '0' && bin[i+1] == '1') {          char ch = bin[i];          bin[i] = bin[i+1];          bin[i+1] = ch;          break;       }    }    if (i == 0)    "No greater number is present";    int j = i+2, k = len-1;    while (j < k) {       if (bin[j] == '1' && bin[k] == '0') {          char ch = bin[j];          bin[j] = bin[k];          bin[k] = ch;          j++;          k--;       }       else if (bin[i] == '0')          break;       else          j++;    }    return bin; } int main() {    string bin = "1011";    cout << "Binary value of next greater number = " << nextBinary(bin); }

Output

Binary value of next greater number = 1101