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

Painless

BinaryGap

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

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:

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


Solve [Proposal 1: Integer.toBinaryString]

image.png

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]

image.png

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


Recommended Posts

[100%] BinaryGap (src & jUnit)
[100%] CyclicRotation (src & jUnit)
[100%] FrogJmp (src & jUnit)
[100%] FrogRiverOne (src & jUnit)
[100%] OddOccurrencesInArray (src & jUnit)
[100%] MinAvgTwoSlice (src & junit)
[100%] PassingCars (src & junit)
[100%] PermCheck (src & junit)
[100%] TapeEquilibrium (src & jUnit)
[100%] [GenomicRangeQuery] (src & junit & author's note)
[100%] MaxCounters (src & junit & author's note)
[100%] Distinct (src & junit & author's note)
[100%] CountDiv (src & junit & author's note)
JUnit 4 notes
JUnit memorandum