Đề bài
Cho một số N. Nhiệm vụ là tìm số lượng phần tử tối thiểu cần loại bỏ ở giữa đến N sao cho XOR thu được từ các phần tử còn lại là tối đa.
Thuật toán
1. Nếu n là 1 hoặc 2 thì không cần loại bỏ phần tử nào. Do đó câu trả lời là 0 2. Tìm một số là lũy thừa của 2 và lớn hơn hoặc bằng n. Gọi số này là nextNumber 2.1. Nếu n == nextNumber hoặc n == (nextNumber – 1) thì câu trả lời là 1 2.2. Nếu n = (nextNumber -2) thì câu trả lời là 0 3. Nếu n là số chẵn thì câu trả lời là 1 ngược lại là 2
Ví dụ
#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; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Numbers to be removed = 1s