BinaryGap at app.codility.com in C Plus Plus Explained - Find longest sequence of zeros in binary representation of an integer
Foreword: Category of Article - Technology, Computers and Software; Algorithm
By: Chrysanthus Date Published: 21 Jan 2024
Problem
Lesson 1 at app.codility.com/programmers
The solution and its explanation are given below.
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.
For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.
Write a function:
int solution(int N);
that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.
For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..2,147,483,647].
Notes
Note that 2,147,483,647 is approximately = 231, which is the maximum integer size for most C++ compilers.
The brute-force (direct) way to do this is to convert the decimal number to a string of 1's and 0's, then look for the binary gaps, and then count the zeros of the longest gap.
A different method, the one used here, continuously divide the decimal number, by 2; and then reading the result from the bottom, as the following table illustrates, for the decimal number, 529 (see below).
Read from the bottom of the table, the answer is, 1000010001. For any division step, there is the dividend divided by the divisor, to give the quotient. The quotient always has a whole number and a remainder. The remainder, may be zero. When converting to base 2, the last quotient is always, zero remainder 1.
The brute force method takes too long. A faster way to solve the problem, as used here, is to begin by assuming that the length of the longest binary gap is 0. This value is stored in a variable. And then while converting to binary, the zeros are counted. When a binary gap is detected, the number of zeros is stored as the maximum gap length, replacing the stored zero. If the next binary gap is longer than this one, then this stored value is replaced by that longer value. If no binary gap is detected in the whole process while converting to binary, then the stored value remains zero.
| Base 2 | Base 10 | Remainder |
| 2 | 529 | |
| 2 | 264 | 1 |
| 2 | 132 | 0 |
| 2 | 66 | 0 |
| 2 | 33 | 0 |
| 2 | 16 | 1 |
| 2 | 8 | 0 |
| 2 | 4 | 0 |
| 2 | 2 | 0 |
| 2 | 1 | 0 |
| 0 | 1 |
The Program Solution
#include <iostream>
using namespace std;
int solution(int N) {
int store = 0;
int count = 0; //counting begins from zero
bool metFirstOne = false; //counting is effective only after the first 1 has been met
while (N/2 >= 0) { //whole number part of quotient
int R = N%2; //modulo to obtain remainder
if (R == 1) {
if (count > store && metFirstOne == true) {
store = count;
count = 0; //reinitialize counter for next possible gap
}
}
if (R == 0) //remainder is 0
count = count + 1;
else {
metFirstOne = true;
count = 0; //reinitialize counter for next possible gap
}
if (N==0)
break;
N = N / 2;
}
return store;
}
int main(int argc, char **argv)
{
int N = 9;
int ret1 = solution(N);
cout << ret1 << endl;
N = 529;
int ret2 = solution(N);
cout << ret2 << endl;
N = 20;
int ret3 = solution(N);
cout << ret3 << endl;
N = 15;
int ret4 = solution(N);
cout << ret4 << endl;
N = 32;
int ret5 = solution(N);
cout << ret5 << endl;
N = 1041;
int ret6 = solution(N);
cout << ret6 << endl;
return 0;
}
There are three if-constructs. The first if-construct should not be typed after the second if-construct.
There are 6 test cases in the above program. The output for the 6 test cases is:
2
4
1
0
0
5
The last if-construct stops (breaks) the loop, when the whole number part of the quotient is zero.
Conclusion
A faster way to solve the problem, is to begin by assuming that the length of the longest binary gap is 0. This value is stored in a variable. And then while converting to binary, the zeros are counted. When a binary gap is detected, the number of zeros is stored as the maximum gap length, replacing the stored zero. If the next binary gap is longer than this one, then this stored value is replaced by that longer value. If no binary gap is detected in the whole process, while converting to zero, then the stored value remains zero.
The reader should register at app.codility.com to be testing his/her own code. At app.codility.com the C++ main() function is not submitted.