C++에서 (n XOR x) =(n – x)인 x <=n 값의 개수

<시간/>

입력으로 숫자 n이 제공됩니다. 목표는 (n xor x)=(nx) 조건이 성립하는 값 x를 찾는 것입니다. 또한 x는 [0,n] 범위에 있습니다.

예를 들어 이해하자

입력 - n=10

출력 − (n XOR x) =(n – x)가 − 4인 x <=n 값의 개수

설명 − 10 x 또는 x =10-x − 0, 2, 8 및 10인 x의 값.

입력 - n=15

출력 − (n XOR x) =(n – x)가 − 16인 x <=n 값의 개수

설명 − 15 x 또는 x =15-x − 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 및 15일 때 x의 값.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

우리는 두 가지 접근 방식을 사용할 것입니다. for 루프를 사용하는 최초의 순진한 접근 방식. 가능한 x에 대해 i=0에서 i<=n으로 순회를 시작합니다. 이제 ( n - i ==(n ^ i) //xor )인지 확인하십시오. true인 경우 카운트가 증가합니다.

정수 변수 n을 입력으로 받습니다.
함수 unique_pair(int arr[], int size)는 배열과 그 길이를 취하고 쌍(arr[i],arr[j])에서 인덱스 i가 되도록 고유한 쌍의 수를 반환합니다.
count의 초기값을 0으로 합니다.
정수 쌍을 포함하는 집합 'se'를 취합니다. (set> se)
두 개의 for 루프를 사용하여 arr[] 순회를 시작합니다. i=0에서 i까지
항상 i를 사용하여 'se'에 쌍 (arr[i],arr[j])을 추가합니다.
두 for 루프의 끝에서 count=se.size()를 업데이트합니다.
이제 Count에는 'se'에 여러 쌍이 있습니다. ( 모두 고유합니다 ).
결과로 카운트를 반환합니다.

효율적인 접근

이 접근 방식에서 우리는 먼저 n을 이에 상응하는 바이너리로 변환할 것입니다. 우리는 알고 있습니다

1 xor 0 =1-0

1 xor 1 =1-1

하지만

0 xor 0 ≠ 0-1

0 xor 1 ≠ 0-1

따라서 n의 이진 표현에서 모든 1에 대해 2개의 경우가 있습니다. n의 이진 표현에서 p개의 경우 조건을 만족하는 2p개의 값이 있습니다.

인덱스 나. 그런 다음 총 고유 쌍에 대해 이러한 개별 수를 추가합니다.

정수 변수 n을 입력으로 받습니다.
함수 unique_pair(int arr[], int size)는 배열과 그 길이를 취하고 쌍(arr[i],arr[j])에서 인덱스 i가 되도록 고유한 쌍의 수를 반환합니다.
count의 초기값을 0으로 합니다.
number=bitset<8>(n).to_string();
을 사용하여 n을 문자열로 변환
length=number.length()를 사용합니다.
for 루프를 사용하여 인덱스 i=0에서 i<길이까지 문자열을 순회합니다. 각 1 증가 카운트에 대해.
count=pow(2,count)를 x의 최종 값으로 설정합니다.
결과로 카운트를 반환합니다.

예(순진한 접근 방식)

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   for (int i = 0; i <= n; i++){
      if (n - i == (n ^ i)){
         count++;
      }
   }
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count of values of x <= n for which (n XOR x) = (n – x) are: 8

예시(효율적인 접근)

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   string number = bitset<8>(n).to_string();
   int length = number.length();
   for (int i = 0; i < length; i++){
      if (number.at(i) == '1')
         { count++; }
   }
   count = (int)pow(2, count);
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -

Count of values of x <= n for which (n XOR x) = (n – x) are: 8