우리에게 num이라는 숫자가 주어지고 작업은 o와 1만 포함하는 주어진 숫자 num을 통해 형성할 수 있는 이진 문자열의 개수를 계산하는 것입니다.
이진법은 숫자 표현 기법의 한 유형입니다. 가장 대중적이고 디지털 시스템에서 사용됩니다. 이진 시스템은 두 가지 작동 상태 또는 가능한 조건만 있는 장치로 나타낼 수 있는 이진 양을 나타내는 데 사용됩니다. 예를 들어 스위치에는 열림 또는 닫힘의 두 가지 상태만 있습니다.
이진 시스템에는 2개의 기호 또는 가능한 숫자 값, 즉 0과 1만 있습니다. 2개의 작동 상태 또는 가능한 조건만 있는 장치로 표시됩니다. 이진 문자열은 이진 값, 즉 0 또는 1을 포함하는 문자열입니다.
예
Input − num = 3 Output − count is 8
설명 - 길이가 3으로 형성될 수 있는 이진 조합은 총 8개이므로 개수는 8이므로 000, 111, 001,101, 100, 110, 011, 010입니다.
Input − num = 2 Output − count is 4
설명 - 길이가 2로 형성될 수 있는 이진 조합은 총 4개이므로 개수는 00, 11, 01,10이므로 개수는 4입니다.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
-
숫자가 임의의 자릿수일 수 있는 긴 유형의 숫자를 입력하십시오.
-
mod 값을 (long long)(le9 + 7)
로 계산합니다. -
개수를 계산하는 함수 만들기
-
count와 다른 변수 temp를 저장할 임시 변수를 선언하고 2로 초기화합니다.
-
숫자를 temp =temp % mod로 설정
-
num> 0
동안 루프 시작 -
IF num &1을 확인한 다음 count를 (count * temp)% mod
로 설정합니다. -
숫자 =숫자>> 1
설정 -
설정 온도 =(온도 * 온도) % 모드
-
반품 횟수
-
결과를 인쇄하십시오.
예시
#include <iostream>
using namespace std;
#define ll long long
#define mod (ll)(1e9 + 7)
// An iterative function to find (x^y)%p in O(log y)
ll power(ll x, ll y, ll p){
ll result = 1;
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0){
// If y is odd, multiply x with result
if (y & 1){
result = (result * x) % p;
}
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return result;
}
// Function to count the number of binary strings
ll countbstring(ll num){
int count = power(2, num, mod);
return count;
}
int main(){
ll num = 3;
cout <<"count is: "<<countbstring(num);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다 -
count is: 8