Computer >> Máy Tính >  >> Lập trình >> C ++

Đếm số giá trị của x <=n mà (n XOR x) =(n - x) trong C ++

Chúng tôi được cung cấp một số n làm đầu vào. Mục đích là tìm các giá trị x sao cho điều kiện (n xor x) =(nx) được giữ nguyên. Ngoài ra x cũng nằm trong khoảng [0, n].

Hãy cho chúng tôi hiểu với các ví dụ

Đầu vào - n =10

Đầu ra - Đếm các giá trị của x <=n mà (n XOR x) =(n - x) là - 4

Giải thích - Giá trị của x với 10 x hoặc x =10-x - 0, 2, 8 và 10.

Đầu vào - n =15

Đầu ra - Đếm các giá trị của x <=n mà (n XOR x) =(n - x) là - 16

Giải thích - Giá trị của x với 15 x hoặc x =15-x - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 và 15.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng tôi sẽ sử dụng hai cách tiếp cận. Cách tiếp cận ngây thơ đầu tiên sử dụng vòng lặp for. Bắt đầu đi ngang từ i =0 đến i <=n với tôi x’s có thể. Bây giờ hãy kiểm tra xem (n - i ==(n ^ i) // xor). Nếu số gia tăng đúng.

  • Lấy biến số nguyên n làm đầu vào.

  • Hàm unique_pair (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các cặp duy nhất sao cho trong cặp (arr [i], arr [j]) index i

  • Lấy giá trị ban đầu của số đếm là 0.

  • Lấy một tập hợp ‘se’ chứa các cặp số nguyên. (đặt > se)

  • Bắt đầu duyệt qua arr [] bằng cách sử dụng hai vòng lặp for. từ i =0 đến i

  • Đối với mỗi cặp luôn là i

  • Ở cuối cả hai vòng lặp for, hãy cập nhật count =se.size ().

  • Đếm bây giờ có một số cặp trong ‘se’. (Tất cả đều là duy nhất).

  • Kết quả là số lượt trả lại.

Phương pháp tiếp cận hiệu quả

Trong cách tiếp cận này, đầu tiên chúng ta sẽ chuyển đổi n thành tương đương nhị phân của nó. Chúng tôi biết rằng

1 xor 0 =1-0

1 xor 1 =1-1

Nhưng

0 xor 0 ≠ 0-1

0 xor 1 ≠ 0-1

Vì vậy, với mỗi 1 trong biểu diễn nhị phân của n, có 2 trường hợp. Đối với p cái trong biểu diễn nhị phân của n, sẽ có giá trị 2p thỏa mãn điều kiện.

chỉ số i. Sau đó, thêm các số lượng riêng lẻ như vậy để có tổng số các cặp duy nhất.

  • Lấy biến số nguyên n làm đầu vào.

  • Hàm unique_pair (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các cặp duy nhất sao cho trong cặp (arr [i], arr [j]) index i

  • Lấy giá trị ban đầu của số đếm là 0.

  • Chuyển n thành chuỗi bằng cách sử dụng number =bitset <8> (n) .to_string ();

  • Lấy length =number.length ().

  • Đảo ngược chuỗi sử dụng vòng lặp for từ chỉ số i =0 đến i <độ dài. Đối với mỗi 1 số gia tăng.

  • Đặt count =pow (2, count) làm giá trị cuối cùng của x.

  • Kết quả là số lượt trả lại.

Ví dụ (cách tiếp cận ngây thơ) 

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 

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

Ví dụ (Phương pháp Tiếp cận Hiệu quả) 

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau - 

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