I've attempted to solve the "BinaryGap" Codility lesson:
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 representation1000010001
and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation10100
and contains one binary gap of length 1. The number 15 has binary representation1111
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.
Here is my solution:
public int solution(int n) {
// write your code in Java SE 8
String binaryRep = Integer.toBinaryString(n);
System.out.println("Binary Representation of " + n + " = " + binaryRep);
List<String> strList = new ArrayList<String>();
int count = 0;
for (int i = 0; i < binaryRep.length(); i++) { // Loop through the each number
String str = binaryRep.charAt(i) + ""; // getting one by one number
if(str.equals("0")){
for(int j = i;j<binaryRep.length();j++){ //Get each next element
String str1 = binaryRep.charAt(j) + "";
if(!str.equals("1") && str.equals(str1)){
if(!strList.isEmpty() && count >= strList.size()){
strList.add(str1);
}else if(strList.isEmpty()){
strList.add(str1);
}
count ++;
}else{
count = 0;
break;
}
}
}
}
return strList.size();
}
Is this solution for Binary Gap is correct or not? What should be improved?
I haven't tested your code yet, but it seems very inefficient if your goal is just counting the longest 'binary gap'.
Problems in your code:
java.lang.String
when it can be just char
. Making objects is much slower than making primitive types.for
loop. For example, let's say you're counting binary gap of 1001
. Then your algorithm counts binary gap of 001
and then 01
. You don't need to count the second one at all. And it's happening becuase you have two for loops.The biggest problem is, that it's possible to solve this problem without converting int
into java.lang.String
at all. And in case you got this problem from a textbook, I believe this is the 'correct' answer: To use bitwise operators.
public static int solution(int num) {
int ptr; //Used for bitwise operation.
for(ptr=1; ptr>0; ptr<<=1) //Find the lowest bit 1
if((num&ptr) != 0)
break;
int cnt=0; //Count the (possible) gap
int ret=0; //Keep the longest gap.
for(; ptr>0; ptr<<=1) {
if((num&ptr) != 0) { //If it's bit 1
ret = cnt < ret ? ret : cnt; //Get the bigger one between cnt and ret
cnt=-1; //Exclude this bit
}
cnt++; //Increment the count. If this bit is 1, then cnt would become 0 beause we set the cnt as -1 instead of 0.
}
return ret;
}