count consecutive 1's in binary

Question

I am writing code in Hackerrank. And recently the problem said, convert decimal to base 2 and then count the max consecutive 1's in the binary number. And first I come with following solution. It works fine. But I do not understand the counting part of it, even though I wrote it.

The code is

int main(){
    int n,ind=0, count=0, mmax=0;
    char bin[100];
    cin >> n;
    while(n){
        if(n%2==0) {
            bin[ind]='0';
            n = n / 2;
            ind = ind + 1; 
            }
        else if(n%2==1) {
            bin[ind]='1';
            n = n / 2;
            ind = ind + 1;    
        }
    }
    for(int i=0; i<=(ind-1); i++){
        if(bin[i] == '1' && bin[i+1] == '1'){
            count++; 
            if(mmax < count)
                mmax = count;
        }
        else
            count=0;
    }
    cout << mmax + 1 << endl;
    return 0;
    }

In the above code, I guess that variable mmax will give me the max consecutive number of 1's but it gives me value that has (max consecutive - 1), So I just wrote like that and submitted the code. But I am curious about. why it is working that way. I am little bit of confused the way that code works like this.

Thanks

`But I do not understand the counting part of it, even though I wrote it.` ... Were you in a trance or something when you wrote it? — Fantastic Mr Fox, Nov 28 '17 at 01:04
@FantasticMrFox https://stackoverflow.com/a/316233/2138219 `//When I wrote this, only God and I understood what I was doing //Now, God only knows` — francium, Nov 28 '17 at 01:10
@FantasticMrFox I believed that variable mmax will give me the result that i wish to get. But when, I compile it, it gives me result less than 1 of the correct result. So I added 1 to the mmax and it worked. After all I became, the one who does not understand it. Yeah, surely only god knows it — Nasantogtokh Amarsaikhan, Nov 28 '17 at 07:21

score 0 · Accepted Answer · answered Nov 28 '17 at 01:09

0

Lets say you have this binary sequence:

Your code will compare starting from the first and second:

|11|110 1 && 1 -> max = 1
1|11|10 1 && 1 -> max = 2
11|11|0 1 && 1 -> max = 3
111|10| 1 && 0 -> max = 3

you can see, that although there are 4 1's you only do 3 comparisons, so your max will always be -1 of the actual max. You can fix this by adding mmax += 1 after your for loop.

answered Nov 28 '17 at 01:09

Fantastic Mr Fox

32,495
27
95
175

Nice explanation, Thanks – Nasantogtokh Amarsaikhan Nov 28 '17 at 07:23

score 0 · Answer 2 · answered Nov 28 '17 at 01:13

Just a little bit of trace using small example will show why.

First, lets say there is only 1 '1' in your array.

Since you require both the current position and your next position to be '1', you will always get 0 for this case.

Let's say I have "11111". At the first '1', since next position is also '1', you increment count once. This repeats until 4th '1' and you increment your count 4 times in total so far. When you reach 5th '1', your next position is not '1', thus your count stops at 4.

In general, your method is like counting gaps between fingers, given 5 fingers, you get 4 gaps.

Side note: your code will fail for the case when there is no '1' in your array.

count consecutive 1's in binary

2 Answers2