นับค่า x ≤ n ที่ทำให้ (n XOR x) = (n – x) ใน C++

เราได้รับตัวเลข n เป็นอินพุต เป้าหมายคือหาค่า x ที่ทำให้เงื่อนไข (n xor x) = (n - x) เป็นจริง โดย 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 เริ่มเดินทางจาก i=0 ถึง i<=n สำหรับ i เป็น x ที่เป็นไปได้ ตรวจสอบถ้า (n - i == (n ^ i)) ถ้าจริงเพิ่ม count

• รับตัวแปรจำนวนเต็ม n เป็นอินพุต
• ฟังก์ชัน unique_pair(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนคู่ที่ไม่ซ้ำซึ่งในคู่ (arr[i],arr[j]) ดัชนี i<j
• กำหนดค่าเริ่มต้นของ count เป็น 0
• สร้างเซต se ที่มีคู่จำนวนเต็ม (set<pair<int, int>> se)
• เริ่มเดินทาง arr[] ด้วยลูป FOR สองชั้น จาก i=0 ถึง i<size-1 และ j=i+1 ถึง j<size
• สำหรับแต่ละคู่ที่มี i<j เพิ่มคู่ (arr[i],arr[j]) เข้า se ด้วย se.insert(make_pair(arr[i], arr[j]))
• ท้ายสุดของลูป FOR ทั้งสอง อัปเดต count=se.size()
• count ตอนนี้มีจำนวนคู่ใน se (ทั้งหมดไม่ซ้ำ)
• คืน count

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้เราจะแปลง 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 ตัว 1 ในการแทนที่ไบนารีของ n จะมีค่า 2^p ที่ทำให้เงื่อนไขเป็นจริง

• รับตัวแปรจำนวนเต็ม n เป็นอินพุต
• แปลง n เป็นสตริงด้วย number=bitset<8>(n).to_string()
• หา length=number.length()
• เดินทางสตริงด้วยลูป FOR จากดัชนี i=0 ถึง i<length สำหรับแต่ละ 1 เพิ่ม count
• กำหนด count=pow(2,count) เป็นค่า x ท้ายสุด
• คืน count

ตัวอย่าง (วิธีง่าย)

#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