[GO] [100%] BinaryGap (src & jUnit)

Painless

BinaryGap

Find the longest sequence of zeros in the binary representation of integers.

Task description

The binary gap in the positive integer N is the maximum sequence of consecutive zeros, with the binary representation of N enclosed in 1s.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. Number 529 has the binary representation 1000010001, which contains two binary gaps, length 4 and length 3. Number 20 has a binary representation of 10100, one binary gap of length 1. The number 15 has the binary representation 1111 and there are no binary gaps. The number 32 has a binary representation of 100000 and no binary gap.

Write a function:

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

** This returns the length of the longest binary gap given the positive integer N. If N does not contain a binary gap, the function must return 0. ** **

For example:

• If N = 1041, then N has the binary representation 10000010001 and its longest binary gap length is 5, so the function must return 5.
• If N = 32, then N has the binary representation "100000" and there are no binary gaps, so the function must return 0.

Write a ** efficient ** algorithm for the following assumptions:

• N is an integer in the [1..2,147,483,647] range.

Solve [Proposal 1: Integer.toBinaryString]

Program BinaryGap.java

BinaryGap.java

    public int solution(int N) {
        int goal = 0;

        String binaryN = Integer.toBinaryString(N);
        char[] charsBinaryN = binaryN.toCharArray();

        int counter = 0;
        boolean counterSwitch = false;
        for (int i = 0; i < charsBinaryN.length; i++) {
            if (charsBinaryN[i] == '0') {
                counterSwitch = true;
                counter++;
            } else if (charsBinaryN[i] == '1') {
                if (counterSwitch) {
                    counterSwitch = false;
                    if (counter > goal) {
                        goal = counter;
                    }
                    counter = 0;
                } else {
                    continue;
                }
            }
        }

        return goal;
    }

junit BinaryGapTest.java

Report trainingC78Z7J-BPG

Solve [Proposal 2: Shift operation]

Program BinaryGapShifter.java

BinaryGapShifter.java

    public int solution(int N) {
        int goal = 0;
        int counter = 0;
        boolean counterSwitch = false;
        while (N > 0) {
            if ((N & 1) == 1) {
                if (counterSwitch) {
                    if (counter > goal) goal = counter;

                    counter = 0;
                } else {
                    counterSwitch = true;
                }
            } else {
                if (counterSwitch) counter++;
            }

            N = N >> 1;
        }

        return goal;
    }

junit BinaryGapShifterTest.java

Report trainingPPEWCY-ENN