Codility Lesson1 - BinaryGap

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.

양의 정수 N 내의 이진 간격은 N의 이진법 표현에서 양 끝에 있는 하나로 둘러싸인 연속적인 0의 최대 시퀀스입니다.

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.

예를 들어, 숫자 9는 이진 표현 1001을 가지며 길이 2의 이진 갭을 포함합니다. 숫자 529는 이진 표현 1000010001을 가지며 길이 4 중 하나와 길이 3 중 하나의 이진 갭을 포함합니다. 숫자 20은 이진 표현 10100을 가지며 길이 1의 이진 갭 하나를 포함합니다. 숫자 15는 이진 표현 1111을 가지며 이진 갭이 없습니다. 숫자 32는 이진 표현 100000을 가지며 이진 갭이 없습니다.

Write a function:

class Solution { public 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.

양의 정수 N이 주어지면 가장 긴 이진 간격의 길이를 반환합니다. N이 이진 간격을 포함하지 않으면 함수는 0을 반환해야 합니다.

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. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

예를 들어, N = 1041일 때, N은 이진 표현 10000010001을 가지므로 가장 긴 이진 간격의 길이가 5이므로 함수는 5를 반환해야 합니다. N = 32일 때, N은 이진 표현 '100000'을 가지므로 이진 간격이 없으므로 함수는 0을 반환해야 합니다.

Write an efficient algorithm for the following assumptions:

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

N은 [1..2,147,483,647] 범위 내의 정수입니다.

---

2023.08.07

class Solution {
    public int solution(int N) {
        int index = 0;
        int newIndex = 0;
        int answer = 0;
        
        String numStr = Integer.toString(N, 2);

        while(index > -1) {
            newIndex = numStr.indexOf("1", index + 1);
            if((newIndex-index) > answer) {
                answer = newIndex-index-1;
            }
            index = newIndex;
        }

        return answer;
    }
}