C++で文字列内の出現頻度が素数となる文字の頻度XORを求める方法

問題の概要

この問題では、1つの文字列が与えられます。求めるのは、文字列に含まれる各文字のうち出現頻度が素数になっているものだけを取り上げ、それらの頻度のXOR(排他的論理和)を計算して出力することです。

具体例を使って問題を確認してみましょう。

入力 − TutorialsPoint

出力 − 3

説明：

• t … 3回出現(3は素数)
• u … 2回出現(2は素数)
• o … 2回出現(2は素数)
• r … 2回出現(2は素数)
• i … 2回出現(2は素数)
• a … 1回出現(1は素数ではない)
• l … 1回出現(1は素数ではない)
• s … 1回出現(1は素数ではない)
• p … 1回出現(1は素数ではない)
• n … 1回出現(1は素数ではない)

素数の頻度を持つ文字は「t」「u」「o」「r」「i」であり、これらの頻度のXORは 3 ^ 2 ^ 2 ^ 2 ^ 2 = 3 となります。

解決アプローチ

この問題は、以下の手順で効率的に解くことができます。

1. 素数表の作成： エラトステネスの篩を用いて、あらかじめ素数かどうかを判定するためのブール型配列を作成しておきます。これにより、任意の数値が素数かどうかをO(1)で判定できます。
2. 頻度の集計： map(連想配列)を使用して、文字列内の各文字の出現回数をカウントします。
3. XORの計算： mapを走査しながら、各文字の頻度が素数表に該当するかを確認します。該当する場合は、その頻度値を結果変数にXORしていきます。
4. 結果の返却： 素数の頻度を持つ文字が1つも存在しない場合は -1 を返し、それ以外は計算されたXORを返します。

実装例

上記の解法をC++で実装したプログラムは以下の通りです。

#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);
   int i, j;
   map<char, int> charFreq;
   for (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<<"The XOR of frequencies of character which have prime frequencies is : ";
   cout<<findPrimeXOR(s);
   return 0;
}

出力

The XOR of frequencies of character which have prime frequencies is : 3

コードの解説

• findPrimes関数： エラトステネスの篩のアルゴリズムを実装しています。0と1を非素数としてマークした後、2から順に各素数の倍数をふるい落としていくことで、指定サイズまでの素数表を構築します。
• findPrimeXOR関数： まず素数表を初期化し、続いてmap<char, int>を使って文字列内の各文字の出現頻度を記録します。その後、mapの全要素を走査し、頻度が素数であればresultにXORを適用します。flag変数は、素数の頻度が少なくとも1つ見つかったことを示すために使用され、1つも見つからなかった場合は -1 を返します。

計算量

• 時間計算量： O(n + M log log M) — nは文字列の長さ、Mは素数表の最大サイズです。文字の頻度集計にO(n)、素数表の生成にO(M log log M)かかります。
• 空間計算量： O(M) — 素数表の配列と、最大でもアルファベット種類数程度のmapが必要になります。