Find longest binary gap in binary representation of integer number.

Find longest length bi-valued slice in an array in java

---

This is a popular interview question asked in Tier-1 companies.

You are given a positive integer n, find the longest distance between two consecutive 1's in the binary representation of n.

Example:

1. Input: 9

Output: 2

9 binary representation is 1001 and there are two 0 in between 1's. so answer is 2

2. Input: 1041
Output: 5
1041 binary representation is 10000010001 and there are 5 consecutive 0's in first gap and 3 consecutive 0's in second binary gap. so answer is 5 as the highest gap among both.

3. Input: 15
Output: 0
15 binary representation is 1111 and there are no 0's in between 1's. so answer is 0

4. Input: 20
Output: 10
20 binary representation is 10100 and contains only one 0 in between 1's. so answer is 1

Algorithm

---

we will take 3 variables 

maxGap: for storing the result

tempGap: for storing temporary gap

oneFlag: a flag for indication that we have encountered 1 before or not.

Example: 101001, in this example when we encounter first binary gap of size 1 which would be in tempGap but later we encountered another binary gap of size 2 which is higher than before, so we need to store previous value of tempGap, that is where maxGap will be used to store whichever is highest among previous binary gaps.

Java Program to find longest binary gap in binary representation of an integer number.

---

package javabypatel;

public class BinaryGap {
    public static void main(String[] args) {
        System.out.println(new BinaryGap().findLongestBinaryGap(20));
    }

    public int findLongestBinaryGap(int number) {
        int maxGap = 0;
        int tempGap = 0;
        boolean oneFlag = false;

        while (number > 0) {
            int remainder = number % 2;
            number = number / 2;
            System.out.print(remainder);
            if (oneFlag) {
                if (remainder == 1) {
                    maxGap = Math.max(tempGap, maxGap);
                    tempGap = 0;
                } else {
                    tempGap ++;
                }
            } else if (remainder == 1) {
                oneFlag = true;
            }
        }
        System.out.println();
        return maxGap;
    }
}

You may also like to see

---

Advanced Java Multithreading Interview Questions & Answers

Type Casting Interview Questions and Answers In Java?

Exception Handling Interview Question-Answer

Method Overloading - Method Hiding Interview Question-Answer

How is ambiguous overloaded method call resolved in java?

Method Overriding rules in Java

Interface interview questions and answers in Java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.