XOR tần suất ký tự là số nguyên tố trong chuỗi C++

Trong bài toán này, cho một chuỗi ký tự, nhiệm vụ là in ra XOR của tần suất xuất hiện của các ký tự mà tần suất đó là số nguyên tố.

Ví dụ:

Input – "tutorialspoint"

Output – 3

Cách làm: kiểm tra tần suất mỗi ký tự, tạo mảng đánh dấu số nguyên tố (sàng Eratosthenes). Lưu tần suất ký tự vào map, so khớp với mảng số nguyên tố. Nếu khớp thì XOR vào kết quả.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

void findPrimes(bool prime[], int p_size) {
    prime[0] = false;
    prime[1] = false;
    for (int p = 2; p * p <= p_size; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= p_size; i += p)
                prime[i] = false;
        }
    }
}

int findPrimeXOR(string s) {
    bool prime[100005];
    memset(prime, true, sizeof(prime));
    findPrimes(prime, 10005);
    
    map<char, int> charFreq;
    for (int i = 0; i < s.length(); i++)
        charFreq[s[i]]++;
    
    int result = 0;
    int flag = 0;
    
    for (auto i = charFreq.begin(); i != charFreq.end(); i++) {
        if (prime[i->second]) {
            result = result ^ i->second;
            flag = 1;
        }
    }
    
    if (!flag)
        return -1;
    return result;
}

int main() {
    string s = "tutorialspoint";
    cout << "XOR tần suất ký tự có tần suất nguyên tố: ";
    cout << findPrimeXOR(s);
    return 0;
}

Kết quả

XOR tần suất ký tự có tần suất nguyên tố: 3