[C++] Interview Question : Bit flip

Question

비트 뒤집기

 

어떤 정수가 주어졌을 때 여러분은 이 정수의 비트 하나를 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라.

 

ex)

input: 1775 ( 11011101111 )
output : 8

 

제약사항

• 고려사항 주어진 정수의 자료형 이 무엇인지 ?  : int로 가정하고 푼다.

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 최소 주어진 정수의 자료형의 가능한 bit수만큼은 탐색해야 한다. 

---

Solution1 (Bruth Force)

가장 쉽게 생각할 수 있는 solution은 모든 0에 1을 넣어보고 가장 긴 연속된 1의 개수를 찾는 것이다. 

그렇다면 0의 개수만큼 반복해야 하기 때문에 가능한 bit의 최대길이가 n이라고 했을 때 시간 복잡도는 O(n^2)이다

Solution2

두번째 방법은 처음부터 끝까지 1의 개수를 세면서, 0을 마주할 경우 해당 0을 1이라 가정하고 계속 count 해 보는 것이다. 만약 해당 bit 다음에 나오는 수가 1이라면 계속해서 count가 될 것이다. 이렇게 진행하며 최대 길이를 갱신해준다.

int solution(int n){
	int longest = 0;
	int count = 0, keep_idx= 0;
	bool change = false;
	for(int i=0; i<32;i++){
		if(((n >> 31-i) & 1) == 1) count++;
		else{
			if(change == false){
				change = true;
				keep_idx = i;
				count++;	
			}else{
				longest = max(longest, count);
				i = keep_idx;
				change = false;
				count = 0;
			}		
		}
	}
	longest = max(longest, count);
	return longest;
}

• Time complexity : O(n)  n 은 비트 수 
• Space Complexity : O(1)