C++에서 연속된 정수가 없는 음이 아닌 정수

양의 정수 n이 있다고 가정합니다. n보다 작거나 같은 음이 아닌 정수를 찾아야 합니다. 제약 조건은 이진 표현이 연속적인 표현을 포함하지 않는다는 것입니다. 따라서 입력이 7이면 답은 5가 됩니다. 5의 이진 표현은 101이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• convert() 함수를 정의하면 n이 필요합니다.
• ret :=빈 문자열
• n이 0이 아닌 동안 −
  • ret :=ret + (n 모드 2)
  • n :=오른쪽 시프트 n, 1회
• 반환
• 메인 방법에서 다음을 수행하십시오. -
• bits :=convert(num) 함수 호출
• n :=비트 크기
• 크기가 n인 배열을 정의하고 크기가 n인 배열을 0으로 정의
• 1[0] :=1, 0[0] :=1
• 초기화 i :=1의 경우, i
• 0[i] :=0[i - 1] + 1[i - 1]
• 일[i] :=0[i - 1]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n >>= 1;
      }
      return ret;
   }
   int findIntegers(int num) {
      string bits = convert(num);
      int n = bits.size();
      vector <int> ones(n);
      vector <int> zeroes(n);
      ones[0] = zeroes[0] = 1;
      for(int i = 1; i < n; i++){
         zeroes[i] = zeroes[i - 1] + ones[i - 1];
         ones[i] = zeroes[i - 1];
      }
      int ret = ones[n - 1] + zeroes[n - 1];
      for(int i = n - 2; i >= 0; i--){
         if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
         else if(bits[i] == '1' && bits[i + 1]== '1') break;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findIntegers(7));
}

입력

7

출력

5