C++でソートされた順序でn番目のバイナリ文字列を検索します

この問題では、正の数1が与えられます。私たちのタスクは、ソートされた順序でN番目の2進文字列を見つけることです。

辞書式順序で並べ替えられた2つの記号aとbのみを使用して作成された文字列の無限のリストからN番目の文字列を見つける必要があります。

リストは-

a、b、aa、ab、ba、bb、aaa、aab、aba、…

問題を理解するために例を見てみましょう

Input : N = 8
Output : aab

ソリューションアプローチ

この問題の簡単な解決策は、ループを使用してn個の文字列すべてを生成することです。そして、N番目の文字列を返します。このソリューションは機能しますが、Nの値が大きい場合に効果的なソリューションを提供することはできません。

そのため、より短時間でソリューションを提供できる別のソリューションが表示されます。

この問題を解決する別のアプローチは、文字列の相対インデックスを使用することです。 2つのシンボルを使用して長さNの文字列の数を生成できるという事実を使用すると、2Nになります。相対インデックスを使用して、バイナリ形式を見つけることができます。 文字列。

相対インデックス=N+ 1-2（floor（log（N + 1）））

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
string findBinString(ll n){
   ll len = (int)log2(n + 1);
   int ri = n + 1 - pow(2, len);
   ll i = 0;
   string binString = "";
   for (i = 0; i < len; i++) {
      binString += 'a';
   }
   i = 0;
   while (ri > 0) {
      if (ri % 2 == 1)
         binString[i] = 'b';
      ri /= 2;
      i++;
   }
   reverse(binString.begin(), binString.end());
   return binString;
}
int main(){
   ll n = 245;
   cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
   return 0;
}

出力

The 245-th binary string in sorted order is bbbabba