티스토리 뷰

원문

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.



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

트렐로 쓰는 법  (0) 2019.03.17
로고 디자인 요청  (0) 2019.01.19
개발환경 setting하기 등  (2) 2018.12.24
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함