Binary Gap
Task
A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.
You simply have to find the length of the maximum run of zeros in the binary representation of the given number.
Solution
It is solved simply with a state machine:
#include <iostream>
using namespace std;
#include <cassert>
enum EState { S_WAIT, S_IN_RUN, S_ONES };
int solution(int N) {
/*states S_IN_RUN = run of zeros found
* S_WAIT = no ones found
* S_ONES = in ones
*/
int state = S_WAIT;
int thisRun = 0, maxRun = 0;
while (N > 0) {
int bit = N % 2;
N = N /2;
if (bit == 1) {
if (state == S_IN_RUN) maxRun = max(maxRun, thisRun);
state = S_ONES;
} else {
switch (state) {
case S_WAIT:
break;
case S_ONES:
state = S_IN_RUN;
thisRun = 1;
break;
case S_IN_RUN:
thisRun++;
break;
default:
assert(false);
}
}
}// while
return maxRun;
}Test Function
This code tests the solution
int main() {
assert(solution(9) == 2);
assert(solution(529) == 4);
assert(solution(20) == 1);
assert(solution(15) == 0);
assert(solution(1041) == 5);
assert(solution(32) == 0);
return 0;
}Results
| Correctness | 100% |
| Performance | – |
One reply on “Codility:BinaryGap Solution”
[…] BinaryGap (100%) […]