จำนวนสมาชิกน้อยที่สุดที่ต้องลบเพื่อให้ XOR สูงสุดด้วย C++

ข้อความโจทย์

กำหนดจำนวน N งานคือหาจำนวนสมาชิกน้อยที่สุดที่ต้องลบระหว่าง 1 ถึง N เพื่อให้ XOR ที่ได้จากสมาชิกที่เหลือเป็นค่าสูงสุด

อัลกอริทึม

1. ถ้า n เป็น 1 หรือ 2 ไม่ต้องลบสมาชิกใดๆ คำตอบคือศูนย์
2. หาจำนวนที่เป็นกำลังของ 2 และมากกว่าหรือเท่ากับ เรียกจำนวนนี้ว่า nextNumber
   2.1. ถ้า n == nextNumber หรือ n == (nextNumber - 1) คำตอบคือ 1
   2.2. ถ้า n = (nextNumber - 2) คำตอบคือ 0
3. ถ้า n เป็นเลขคู่ คำตอบคือ 1 มิฉะนั้นคือ 2

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

#include <iostream>
using namespace std;

int nextPowerOf2(int n) {
    if (n && !(n & (n - 1))) {
        return n;
    }
    int cnt = 0;
    while (n) {
        n = n / 2;
        ++cnt;
    }
    return (1 << cnt);
}

int elmentsToBeRemoved(int n) {
    if (n == 1 || n == 2) {
        return 0;
    }
    int nextNumber = nextPowerOf2(n);
    if (n == nextNumber || n == nextNumber - 1) {
        return 1;
    } else if (n == nextNumber - 2) {
        return 0;
    } else if (n & 1) {
        return 2;
    } else {
        return 1;
    }
}

int main() {
    int n = 10;
    cout << "Numbers to be removed = " << elmentsToBeRemoved(n) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Numbers to be removed = 1