จำนวนค่าของ x <=n ซึ่ง (n XOR x) =(n – x) ใน C++

เราได้รับตัวเลข n เป็นอินพุต เป้าหมายคือการหาค่า x ที่เงื่อนไข (n xor x)=(nx) ถืออยู่ x ยังอยู่ในช่วง [0,n].

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − n=10

ผลผลิต − จำนวนค่าของ x <=n ซึ่ง (n XOR x) =(n – x) คือ − 4

คำอธิบาย − ค่าของ x ที่มี 10 xor x =10-x − 0, 2, 8 และ 10

ป้อนข้อมูล − n=15

ผลผลิต − จำนวนค่าของ x <=n ซึ่ง (n XOR x) =(n – x) คือ − 16

คำอธิบาย − ค่าของ x ที่มี 15 xor x =15-x − 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 และ 15

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

เราจะใช้สองวิธี วิธีไร้เดียงสาครั้งแรกที่ใช้ for loops เริ่มต้นการเดินทางจาก i=0 ไปยัง i<=n for i เท่าที่เป็นไปได้ x's ตอนนี้ตรวจสอบว่า ( n - i ==(n ^ i) //xor ) ถ้านับเพิ่มจริง

• รับตัวแปรจำนวนเต็ม n เป็นอินพุต

• ฟังก์ชัน unique_pair(int arr[], int size) รับอาร์เรย์และความยาวและส่งคืนจำนวนคู่ที่ไม่ซ้ำซึ่งในคู่ (arr[i],arr[j]) ดัชนี i

• ใช้ค่าเริ่มต้นนับเป็น 0

• ใช้เซต 'se' ที่มีคู่จำนวนเต็ม (set> se)

• เริ่มสำรวจ arr[] โดยใช้ two for loops จาก i=0 ถึง i<ขนาด-1 และ j=i+1 ถึง j<ขนาด

• สำหรับแต่ละคู่เสมอ i

• ในตอนท้ายของทั้งสองลูป ให้อัปเดต 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

ดังนั้นสำหรับทุกๆ 1 ในการแทนค่าไบนารีของ n จะมี 2 กรณี สำหรับ p ที่แทนค่าไบนารีของ n จะมีค่า 2p ที่ตรงตามเงื่อนไข

ดัชนี ผม. จากนั้นเพิ่มจำนวนดังกล่าวเป็นรายบุคคลสำหรับคู่ที่ไม่ซ้ำทั้งหมด

• รับตัวแปรจำนวนเต็ม n เป็นอินพุต

• ฟังก์ชัน unique_pair(int arr[], int size) รับอาร์เรย์และความยาวและส่งคืนจำนวนคู่ที่ไม่ซ้ำซึ่งในคู่ (arr[i],arr[j]) ดัชนี i

• ใช้ค่าเริ่มต้นนับเป็น 0

• แปลง n เป็นสตริงโดยใช้ number=bitset<8>(n).to_string();

• ใช้ length=number.length()

• สตริงสำรวจโดยใช้ for วนซ้ำจากดัชนี i=0 ถึง i

• ตั้งค่า 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