본문 바로가기

스타트업

코딜리티 문제 - 바이너리갭(binary gap)구하기 번역

728x90

원문

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.

Write a function:


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.

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.

Assume that:

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

Complexity:

expected worst-case time complexity is O(log(N));

expected worst-case space complexity is O(1).


번역

바이너리갭은 자연수 N을 이진법으로 바꾸었을 때 양 끝이 1로 둘러싸인 연속되는 0이 연속되는 최대의 자리수이다.


예를들어 9는 1001인데 바이너리 갭이 2이다. 529는 이진수로 표현하면 1000010001인데 여기에는 바이너리갭이 2개 존재하는데 하나는 4이고 다른 하나는 3이다. 20은 이진수로 바꾸면 10100인데 1개의 바이너리갭이 있다. 15는 이진수로 표현하면 1111인데 바이너리갭이 없다.


자연수 N을 입력받아서 최대 길이의 바이너리갭을 리턴하는 함수를 만들어라. 바이너리갭이 없을 경우에는 0을 리턴한다.

예를들어 입력받은 N = 1041인 경우 5를 리턴하면 된다. 1041은 이진수로 10000010001이기 때문이다.


N은 1 ~ 2,147,483,647 사이의 수 이다.

worst-case 시간 복잡도는 O(log(N)) 이고

worst-case 공간 복잡도는 O(1)이다.


end.



728x90

'스타트업' 카테고리의 다른 글

트렐로 쓰는 법  (0) 2019.03.17
로고 디자인 요청  (0) 2019.01.19
개발환경 setting하기 등  (2) 2018.12.24
코딜리티 문제 - 바이너리갭(binary gap)구하기 번역  (0) 2018.10.04
블로그 주인장입니다. 원하시는 정보는 얻으셨나요? 이 포스트에서 추가로 필요한 정보가 있으시면 여기에 남겨주세요.