Cho hai số S và K. Mục tiêu là tìm các cặp có thứ tự của số dương sao cho tổng của chúng bằng S và XOR bằng K.
Ta thực hiện bằng cách bắt đầu từ i=1 đến i<S-1 và j=i+1 đến j<S. Nếu bất kỳ cặp (i,j) nào có sum==S và i^j==K (XOR). Thì tăng count thêm 2 vì (i,j) và (j,i) đều được tính là cặp khác nhau.
Hãy hiểu qua các ví dụ.
Đầu vào
S=10 K=4
Đầu ra
Cặp có thứ tự tổng S và XOR K: 2
Giải thích
Các cặp: (3,7) và (7,3)
Đầu vào
S=12 K=6
Đầu ra
Cặp có thứ tự tổng S và XOR K: 0
Giải thích
Không có cặp nào thỏa mãn.
Phương pháp sử dụng trong chương trình dưới đây
- Nhận số nguyên S và K.
- Hàm
sumXOR(int s, int k)nhận s và k trả về số cặp có thứ tự với sum=s và xor=k. - Khởi tạo biến count = 0 cho cặp.
- Duyệt bằng hai vòng lặp for để tạo cặp.
- Bắt đầu từ i=1 đến i<s. Và j=i+1 đến j<s-1.
- Với mỗi cặp (i,j) kiểm tra nếu (i+j==s) && (i^j==k). Nếu đúng tăng count 2 vì (i,j) và (j,i) là hai cặp khác nhau.
- Sau tất cả vòng lặp count chứa tổng số cặp như vậy.
- Trả về count làm kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int sumXOR(int s, int k) {
int count = 0;
for (int i = 1; i < s; i++) {
for(int j = i+1; j < s-1; j++) {
if( (i+j) == s && (i^j) == k ) {
count += 2; // (i,j) và (j,i) là hai cặp
}
}
}
return count;
}
int main() {
int S = 9, K = 5;
cout << "Cặp có thứ tự tổng S và XOR K: " << sumXOR(S, K);
return 0;
}
Đầu ra
Nếu chạy mã trên sẽ cho kết quả sau:
Cặp có thứ tự tổng S và XOR K: 4