ค่า XOR สูงสุดโดยใช้ K ตัวเลขจาก 1 ถึง n ใน C++

ในปัญหานี้ เราได้รับจำนวนเต็มบวกสองจำนวน n และ k งานของเราคือหา XOR สูงสุดระหว่าง 1 ถึง n โดยใช้สูงสุด X ตัวเลข

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:

อินพุต - n = 5, k = 2

เอาต์พุต - 7

คำอธิบาย -

elements till 5 is 1, 2, 3, 4, 5
Selecting all XOR pairs:
1^2 = 3, 1^3 = 2, 1^4 = 5, 1^5 = 4
2^3 = 4, 2^4 = 6, 2^5 = 7
3^4 = 7, 3^5 = 6
4^5 = 1
The maximum here is 7.

ในการแก้ปัญหานี้ ค่า XOR สูงสุดสามารถหาได้สำหรับการจัดหมู่ใดๆ ของตัวเลขเมื่อบิตทั้งหมดของตัวเลขถูกตั้งค่า (set)

ดังนั้น ถ้าตัวเลขคือ 5 ไบนารีคือ 101 ค่า XOR สูงสุดจะเป็น 111 คือ 7

แต่ถ้าจำนวนองค์ประกอบที่จะนำไปหา XOR สูงสุดคือ 1 แล้ว max XOR คือ 1 มิฉะนั้น ค่า XOR สูงสุดจะหาได้โดยการตั้งบิตทั้งหมดให้เป็น 1

ตัวอย่างโค้ด

โปรแกรมแสดงการทำงานของวิธีแก้ปัญหาของเรา:

#include <iostream>
using namespace std;

int maxXor(int n, int k) {
    if (k == 1)
        return n;
    int result = 1;
    while (result <= n)
        result <<= 1;
    return result - 1;
}

int main() {
    int n = 5, k = 2;
    cout<<"The maximum XOR of "<<k<<" numbers from 1 to"<<n<<" is "<<maxXor(n, k);
    return 0;
}

ผลลัพธ์

The maximum XOR of 2 numbers from 1 to 5 is 7