'Binary Gap Program in Java

My problem statement:

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.

My code:

public class Abc {

    static void decToBinary(int n) {

        int[] binaryNum = new int[1000];

        // counter for binary array 
        int i = 0;
        while (n > 0) {
            // storing remainder in binary array 
            binaryNum[i] = n % 2;
            n = n / 2;
            i++;
        }
        int ctr = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<Integer>();

        // printing binary array in reverse order 
        for (int j = i - 1; j >= 0; j--) {
            System.out.print(binaryNum[j]);
            if (binaryNum[j] == 0) {
                k = j;
                do {
                    ctr++;
                    k++;
                } while (binaryNum[k] == 0);
                al.add(ctr);
                ctr = 0;
            }
        }

        for (int ii = 0; ii < al.size(); ii++) {
            System.out.println(al.get(ii));
        }
    }

    // driver program 
    public static void main(String[] args) {
        int n = 1041;
        decToBinary(n);
    }
}

I am trying to show the output of binary gap that is stored in my ArrayList. But the output is quite different for a given input of 1041. I don't know why it is storing 1,2,3,4; according to my logic it should store only the gap values 5 and 3 in case of input:1041, even though 5 and 3 are also stored in the ArrayList but at some other index.

I think there is a problem in the do-while loop especially in al.add(ctr) but I haven't figured it out yet.

Solution 1:^[1]

If this is for homework, your problem is here:

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            k = j;
            do {
                ctr++;
                k++;
            } while (binaryNum[k] == 0);
            al.add(ctr);
            ctr = 0;
        }
    }

Note that:

You update k as you go along, but you don't update j, so you get 1 through whatever the proper value is ([1, 2, 3, 4, 5, 1, 2, 3] instead of [5, 3]).
You don't need k at all.

    for (int j = i - 1; j >= 0; j--) {
        if (binaryNum[j] == 0) {
            int ctr = 0;
            while (binaryNum[j] == 0) {
                ctr++;
                j--;
            }
            al.add(ctr);
        }
    }

This is shown to work here.

If you're not doing this for homework, and you need performance for a real-world use, use Java's built-in bitwise methods in the Integer class, which use very, very fast CPU instructions on CPUs that have them:

import java.util.Arrays;

public class Abc {
    public static final int[] gaps(int n) {
        // The number of gaps is the number of one bits minus one.
        final int[] result = new int[Math.max(0, Integer.bitCount(n) - 1)];
        
        // Remove the last one bit and all bits after to get to first gap.
        n >>>= Integer.numberOfTrailingZeros(n) + 1;
        
        for (int i = result.length - 1; i >= 0; i--) {
            final int gapSize = Integer.numberOfTrailingZeros(n);
            result[i] = gapSize;
            // Remove the last one bit and all bits after to get to next gap.
            n >>>= gapSize + 1;
        }
        
        return result;
    }
    
    // Driver program 
    public static void main(final String[] args) {
        final int n = 1041;
        System.out.println(Integer.toBinaryString(n));
        System.out.println(Arrays.toString(gaps(n)));
    }
}

This is shown to work here.

Solution 2:^[2]

The solution below gave me 100%:

class Solution {
        public int solution(int N) {
            String value = Integer.toBinaryString(N);
            int counter = 0;
            List<Integer> counters = new ArrayList<>();
            for (int i = 0; i < value.length(); i++) {
                char current = value.charAt(i);
                if (current == '0') {
                    counter += 1;
                } else {
                    counters.add(counter);
                    counter = 0;
                }
            }
            return Collections.max(counters);
        }
    }

Solution 3:^[3]

I got perfect 100 with this answer. Hope this will help you.

public int solution(int N) {
        String binary = Integer.toBinaryString(N);
        int count = 0;
        int tmpCount = 0;
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '0') {
                if (i > 0 && binary.charAt(i - 1) == '1') {
                    tmpCount++;
                } else {
                    if (tmpCount > 0) tmpCount++;
                }
            } else if (binary.charAt(i) == '1') {
                if (tmpCount > 0 && tmpCount > count) {
                    count = tmpCount;
                }
                tmpCount = 0;
            }
        }
        return count;
    }

Solution 4:^[4]

var k should be also decreased, because j decreases, also after iteration has completed you should assign j = k. and you have to check if k is greater or equals to zero while (k >= 0 && binaryNum[k] == 0);, otherwise you get ArrayIndexOutOfBoundsException. also you have to check if k is less than zero to count binary gaps properly if(k < 0) {j = k;break;}

  for (int j = i - 1; j >= 0; j--) {
        System.out.print(binaryNum[j]);
        if (binaryNum[j] == 0) {
            k = j;
            do {
                ctr++;
                k--;
            } while (k >= 0 && binaryNum[k] == 0);
            if(k < 0) {
                j = k;
                break;
            }
            al.add(ctr);
            ctr = 0;
            j = k;
        }
    }

Solution 5:^[5]

//working 100% with all the test cases

public static void main(String ar[]) {
        Integer val = 10092;
        String vals = val.toBinaryString(val);
        int gapVal = findBinaryGap(vals);
        System.out.println(vals);
        System.out.println("gapVal=" + gapVal);

    }

public static Integer findBinaryGap(String binVal) {
        Integer retVal = 0;
        String splitVal[] = binVal.split("1");
        int endVal = splitVal.length;
        if (binVal.endsWith("0")) {
            endVal = endVal - 1;
        }
        for (int incr = 0; incr < endVal; incr++) {
            if (retVal < splitVal[incr].length()) {
                retVal = splitVal[incr].length();
            }
        }
        return retVal;
    }

Solution 6:^[6]

Try the below codes,

public int solution(int n) {
    String binaryString = Integer.toBinaryString(n);
    int count = 0, bigGap = 0, temptCount = 0;
    for (int i = 0; i < binaryString.length(); i++) {
        char c = binaryString.charAt(i);
        if (c == '0') {
            temptCount++;
        } else {
            count = temptCount;

            if (count > bigGap) {
                bigGap = count;
            }
            temptCount = 0;
        }

    }

    return bigGap;
}

Solution 7:^[7]

Try this one, I got 100%

public int solution(int N) {
    String binaryNumber = Integer.toBinaryString(N);

    String[] gaps = binaryNumber.replaceAll("0+$", "").split("1");


    int maxLength = 0;
    for (String gap: gaps) {
        if (gap.length() > 0 && gap.length() > maxLength) {
            maxLength = gap.length();
        }
    }
    return maxLength;
}

Solution 8:^[8]

All tests passed in Codility.

public class BinaryGap {

  public static void main(String ar[]) {
   Integer val = 328;

   int gapVal = findBinaryGap(val);
   System.out.println("gapVal=" + gapVal);

 }

 public static Integer findBinaryGap(Integer binVal) {

  String values = Integer.toBinaryString(binVal);
  String[] splitVal = values.substring(0, values.lastIndexOf("1")).split("1");

  if (Arrays.stream(splitVal).noneMatch(v -> v.length() > 0)) {
    return 0;
  }

   return java.util.Arrays.stream(splitVal).mapToInt(String::length)
                       .max().orElse(0);
 }

}

Solution 9:^[9]

My solution 100%

public class Solution {
public int solution( int N ){

    String rep = "";
    String[] zoros = null;
    int maxi = 0;

    try{
        if( N < 5 ){ return maxi; } // 5 is the first positive integer that contains a bi-gap

        rep = Integer.toBinaryString(N);
        zoros = rep.split("1");

        // deal with edges
        if(!rep.startsWith("1")){ zoros[0] = ""; }
        if(!rep.endsWith("1")){ zoros[zoros.length - 1] = "";}
        
        //now looper
        for( int i = 0; i < zoros.length ;i++ ){
            if(zoros[i].length() > maxi){
                maxi = zoros[i].length();
            }
        }
    } 
    catch( Exception e ){ 
        System.console().writer().println(e.getMessage()); 
    }
    System.console().writer().println("Neo-Maxi Zoomdweebie: " + Integer.toString(maxi));
    return maxi;
}
}

Solution 10:^[10]

another solution that I did and it works totally fine

public int solution(int N) {
        String value = Integer.toBinaryString(N);
        String[] a = value.split("1");
        if (value.endsWith("0")) {
            a = Arrays.copyOf(a, a.length-1);
        }
        OptionalInt finalResult = Arrays.stream(a).filter(h -> h.length() > 0).mapToInt(String::length).max();

        return finalResult.isPresent() ? finalResult.getAsInt() :  0;
    }

Solution 11:^[11]

on codility, my solution for BinaryGap "problem" was

public int solution(int N) {
        //get binary representation
        String binaryRep = Integer.toBinaryString(N);
        //cut last zeros since they aren't between "1"
        if (!binaryRep.endsWith("1")) {
            final int i = binaryRep.lastIndexOf("1");
            binaryRep = binaryRep.substring(0, i);
        }

        //count the longest zero string
        String[] binaryBlocks = binaryRep.split("1");
        int result = 0;
        for (String binaryBlock : binaryBlocks) {
            int binaryBlockLength = binaryBlock.length();
            if (binaryBlockLength > result) {
                result = binaryBlockLength;
            }
        }
        return result;
    }

Hope it helps! :)

Solution 12:^[12]

public int solution(int N){
    try {
        return Collections.max(Arrays.asList(Integer.toBinaryString(N)
                .replaceAll("0+$", "").split("1"))
                .stream().mapToInt(String::length).boxed()
                .collect(Collectors.toList()));
    }catch (NoSuchElementException e){
        return 0;
    }
}

"0+$" - replacing all trailing zeros

Solution 13:^[13]

This solution gave me 100% score, I used indexOf to get the first index of 1, then get the first second index of 1 and calculate the difference between them, this gives me a substring of 0s, save the length of that substring and then calculate the second substring of 0s as we did before and so, at every time you calculate the substring make sure to pick the longest one.

class Solution {
    public int solution(int N) {
        String bin = intToBinary(N);
        int firstOne = bin.indexOf('1');
        int cnt = 0;
        
        for(int i=firstOne; i<bin.length(); ++i){
            int sec = bin.indexOf('1', i);
            cnt = Math.max(sec-firstOne-1, cnt);
            firstOne = sec;
        }
        return cnt;
        
    }
    
    private static String intToBinary(int N){
        String s = "";
        while(N>0){
            s = ( (N%2) == 0 ? "0" : "1") + s;
            N = N / 2;
        }
        return s;
    }
}

Solution 14:^[14]

This one was easiest to understand IMO

class Solution {
    public int solution(int N) {
        int gapSize = 0;
        int tempCount = 0;
        String s = Integer.toBinaryString(N);

/* You can start the loop from index 1, since all binary numbers
except 0 start with 1 and 0 is covered by initializing the variables (saves 2 conditions) */
        for(int i = 1; i < s.length(); i++) {
            if(s.charAt(i) == '0') {
                tempCount++; // count the number of 0
            } else if(s.charAt(i) == '1') {  // when 1 is found
                if(tempCount > gapSize) {    // and gap is smaller than the now measured one
                    gapSize = tempCount;     // record the so far biggest gap
                }
                tempCount = 0;               // reset the counter when 1 is found
            }
        }
        return gapSize;
     }
}

Solution 15:^[15]

By the way , this is respective solution in KOTLIN, If anyone is interested.

I first converted the Number to Binary String and then convert binary String to a char Array , Then I loop through forEachIndexed loop and try to find the indices of 1 and save them in an oneIndicesArrayList and also check the newGap , if the newGap is greater than maxGap , I assign the newGap value to maxGap otherwise maxGap would keep the old value. This works perfect and score was 100%.

fun solution(N: Int): Int {
        // write your code in Kotlin
        val binaryStr = toBinary(N)
        val charArray = binaryStr.toCharArray()


    var maxGap = 0
    var oneIndicesArray = arrayListOf<Int>() 
    charArray.forEachIndexed { index, element ->
        
        if(element == '1') {
            if(oneIndicesArray.isNotEmpty()) {
               val newGap =  (index - oneIndicesArray[oneIndicesArray.size - 1]) - 1
                if(newGap > maxGap) maxGap = newGap
            }
            oneIndicesArray.add(index)
        }
    }
    return maxGap
}

fun toBinary(decimalNumber: Int, binaryString: String = "") : String {
    while (decimalNumber > 0) {
        val temp = "${binaryString}${decimalNumber%2}"
        return toBinary(decimalNumber/2, temp)
    }
    return binaryString.reversed()
}

Solution 16:^[16]

I got 100% score on this one

fun solution(N: Int): Int {
// write your code in Kotlin
var maxNumber= 0
val binary= Integer.toBinaryString(N)
val split= binary.split("1")
val loop= if(binary.endsWith("1")) split.size else split.size-1
for (s in 0 until loop){
    maxNumber=Integer.max(maxNumber, split[s].length)
}
return maxNumber

}

Solution 17:^[17]

public static int solution(int N) {
    // write your code in Java SE 8
    int result = 0;
    int prev = 0;
    int diff;
    int length = (int)(Math.ceil(Math.log(N) / Math.log(2)));
    int[] binary=new int[length];
    for(int i = length-1;i > -1;i--,N /= 2) binary[i] = N % 2;
    for(int i = 0;i < length;i++){
        if(binary[i] == 1){
            diff = i - prev;
            result = diff > 1 && diff > result ? diff - 1 : result;
            prev = i;
        }
    }
    return result;
}

Solution 18:^[18]

public int solution(int N) {
 String binaryNo = Integer.toBinaryString(N);
 int firstIndex = binaryNo.lastIndexOf("1");
 int currentGap = 0;
 int biggestGap = 0;
 for (int i = firstIndex; i >= 0; i--) {
  if (getNthDegit(binaryNo, i) == 0) {
   currentGap++;
  } else {
   if (biggestGap < currentGap) {
    biggestGap = currentGap;
   }
   currentGap = 0;
  }
 }
 return biggestGap;
}

public static int getNthDegit(String number, int position) {
 String numberString = "" + number;
 char c = numberString.charAt(position);
 return Character.getNumericValue(c);
}

Solution 19:^[19]

Python style solution and it got 100% score:

public static int solution(int N) {      
    List<String>result = Arrays.asList(Integer.toBinaryString(N).replace("0"," ").strip().split("1")); 
    if(!result.isEmpty()){
         return Collections.max(result.stream().map(String::length).collect(Collectors.toList()));
    }        
     return 0;   
}

Solution 20:^[20]

The following code gives the 100% solution for the same problem in javascript. Also I have added console logs which show the flow and results before returning. This problem is to return the maximum binary gap of 0's from a binary number which we obtain from decimal numbers. Flow:

function that converts given decimal into binary equivalent number and store each value of binary into an array. then return the same array.
function to evaluate the number of gaps of 0's in the returned array.

check the maximum gap, if available then return the max number. Else return 0;

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 8.9.4)
    const aBi = returnBinary(N);
    var gaps = [];
    var flag = false;
    var counter = null;
    for(var digit in aBi){
        
        let nexdigit= parseInt(digit) + 1; 
        if(aBi[digit]===1 && aBi[nexdigit] === 0 ){
            flag = true;counter=0;
        }
        if(flag === true){
            counter +=1;
          }
        if(aBi[digit]===0 && aBi[nexdigit] === 1 ){
            counter-=1;
            gaps.push(counter);
              counter = null;
        }
    }
    let max;
    if(gaps[0]!== undefined){
     max = gaps[0];
    }
    else {
    console.log(0);
         return 0;
         }
for(var i = 1; i < gaps.length;i++){
 if(max < gaps[i] ){ max = gaps[i] }
}
console.log(max);
return max;
}

function returnBinary(nDeccimal){
 var aBinary = [];
if(nDeccimal > 0){
// this will return a binary sequence of numbers of given number and will return as a string.
while(nDeccimal >= 1){
let remainder = nDeccimal % 2;
aBinary.unshift(remainder);
nDeccimal = parseInt(nDeccimal / 2);
}
}
console.log(aBinary.join(""));
return aBinary;
}
console.log("#####Test One ######");
solution(24);
console.log("######Test Two #####");
solution(98);

Solution 21:^[21]

Binary Gap in java when you enter 529 binary is 1000010001 and large gap is4 and for 32 number binary is 100000 no binary gap (0)

public class BinaryGap {    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("please enter number");
        int positiveInt = scanner.nextInt();
        char c[] = Integer.toBinaryString(positiveInt).toCharArray();
        System.out.println(c);
        int count=0;
        int temp = 0;
        for (int i = 0; i < c.length; i++) {
            if(c[i] == '0') {
                count++;
            } else if(count > 0 && count > temp) {
                temp = count;
                count =0;
            }
        }
        System.out.println(temp);
    }
   }

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution	Source
Solution 1
Solution 2	Marcos Mitozo
Solution 3	Gilbert Parreno
Solution 4
Solution 5	Rathakrishnan Duraimoni
Solution 6	Ã–mer Erden
Solution 7	El Atendedor
Solution 8	Suman Mitra
Solution 9	John Kelly
Solution 10	M-sAnNan
Solution 11	lombocska
Solution 12
Solution 13	Abdelrahman Ibrahim
Solution 14	Taslim Oseni
Solution 15
Solution 16	Owais
Solution 17	Yitbareck
Solution 18	Kathees
Solution 19	DankDizaster
Solution 20
Solution 21	Mohsin AR

'Binary Gap Program in Java

Solution 1:[1]

Solution 2:[2]

Solution 3:[3]

Solution 4:[4]

Solution 5:[5]

Solution 6:[6]

Solution 7:[7]

Solution 8:[8]

Solution 9:[9]

Solution 10:[10]

Solution 11:[11]

Solution 12:[12]

Solution 13:[13]

Solution 14:[14]

Solution 15:[15]

Solution 16:[16]

Solution 17:[17]

Solution 18:[18]

Solution 19:[19]

Solution 20:[20]

Solution 21:[21]