Happy Monday! It is another cold fall day in the Twin Cities of Minneapolis and St. Paul. In the past few days I have been solving a few problems from the Developer Training section in the Codility_ website. As I have mentioned several times, it takes time to write these posts. I usually do not solve more than one problem a day. I am doing so and will continue until I complete all the problems posted in the Codility_ Developer Training Lessons section. So in order to save some precious time, I will be limiting my chit-chat to a sentence or two.
I am also starting to look at tools and equipment to start my YouTube channel. Planning on getting my first post early in January 2022. Will see how that goes.
Now to the main subject of the post.
BinaryGap Find longest sequence of zeros in binary representation of an integer.
The problem name provides a flavor of what the problem is about. In this case we are given a sequence of zeros in a binary representation of an integer. We need to return the number of zeroes in the longest sequence.
If interested in this problem, I suggest you visit Codility_ and get the current requirements from the site. The descriptions seem to be quite verbose and contain a lot of useful information.
We will be solving this problem using the Java programming language and the VSCode IDE on a Windows platform. Since we will not be using the Codility- online IDE, we will require a simple test scaffold. Such code is NOT PART OF THE SOLUTION.
18 main <<< n: 18 <<< n: 9 gap: 0 <<< n: 4 gap: 0 <<< n: 1 gap: 2 main <<< output: 2 1041 main <<< n: 1041 <<< n: 1041 gap: 0 <<< n: 520 gap: 0 <<< n: 65 gap: 3 <<< n: 1 gap: 3 <<< n: 0 gap: 3 <<< n: 0 gap: 3 main <<< output: 3 15 main <<< n: 15 <<< n: 15 gap: 0 <<< n: 7 gap: 0 <<< n: 7 gap: 0 <<< n: 3 gap: 0 <<< n: 1 gap: 0 <<< n: 1 gap: 0 main <<< output: 0 32 main <<< n: 32 <<< n: 1 gap: 0 <<< n: 0 gap: 0 <<< n: 0 gap: 0 main <<< output: 0
The input line holds an integer. That value needs to be passed to the function of interest. Our function of interest should return the desired results.
Our test scaffold seems to read the input line, populate a variable and then display it. This is done to verify that all is well before calling the function of interest.
A set of lines follow. The last one is from our test code displaying the result. The intermediate lines are generated by our implementation of the function of interest. They are used to follow our implementation.
There are four test cases in this screenshot. I believe all came from Codility_.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read n ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< n: " + n);
// **** call function of interest ****
System.out.println("main <<< output: " + binaryGap(n));
}
Our test scaffold reads the input line and extracts the integer `n`. The function of interest is called and the returned result is displayed. Simple and to the point.
/**
*
*/
static int binaryGap(int N) {
// **** initialization ****
int maxGap = 0;
int gap = 0;
int n = N;
// ????? ????
System.out.println("<<< N: " + Integer.toBinaryString(N));
// **** traverse the bits in `N` - O(n) ****
while (n > 0) {
// **** look for starting 1 ****
while (n > 0 && n % 2 == 0) {
// ???? ????
System.out.println("<<< n % 2: " + n % 2 + " n: " + n);
// **** skip this 0 ****
n /= 2;
}
// ???? ????
System.out.println("<<< n: " + n + " gap: " + gap);
// **** skip current 1 ****
n /= 2;
// ???? ????
System.out.println("<<< n: " + n + " gap: " + gap);
// **** look for ending 1 (count gap) ****
while (n > 0 && n % 2 == 0) {
// ???? ????
System.out.println("<<< n % 2: " + n % 2 + " n: " + n);
// **** count this 0 ****
gap++;
// **** skip this 0 ****
n /= 2;
}
// ???? ????
System.out.println("<<< n: " + n + " gap: " + gap);
// **** update max gap ****
maxGap = Math.max(gap, maxGap);
// **** reset gap ****
gap = 0;
}
// **** return the maximum gap ****
return maxGap;
}
We start by initializing some variables. The `maxGap` is used to hold the value we will return in this function. The `gap` will be used to track the number of zeros in the current gap. I tend to reserve uppercase identifiers for constants. In this case the argument is in uppercase so a lowercase version is used.
We then enter a loop which will process `n`.
We look for the starting 1. Note that the starting 1 represents the lowest bit in `n` when it is a 1. Note that we are dividing `n` by 2 in each pass.
Now that we found the first 1, we divide `n` by 2 to remove it and start counting `0`s.
It is possible that the current 1 might be followed by another 1.
In the next loop we continue dividing `n` and counting the number of 0s in the variable gap.
Two things may happen. We find the next 1 or run out of bits to process. One way or the other, we need to check the value of `gap` against the `maxGap`. What we are required to do is to return the value of the maximum gap.
In preparation for the next loop we clear the value in `gap`.
The process continues until the `n` in the main loop reaches the value 0.
The last thing is to return the value in `maxGap`.
Note that the Execution is O(n) where n is the number of bits in N. The Space is O(1) since we just require a couple variables.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
Please note that the code here presented might not be the best possible solution. In most cases, after solving the problem, you can take a look at the best accepted solution provided by the different websites (i.e., HackerRank, LeetCode).
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John