C++でパリンドロームを形成するために要素を再配置できるサブ配列の数

整数要素の配列が与えられ、その要素が有効な回文を形成できるように、与えられた配列から形成できるサブ配列の数を計算することがタスクです。回文は、最初と最後から同じように配置されたシーケンスです。

入力 − int arr [] ={3、3、1、4、2、1、5}

出力 −要素を再配置してパリンドロームを形成できるサブアレイの数は− 9

説明 −要素を配置して回文を形成できる有効なサブ配列は、{3}、{3}、{1}、{4}、{2}、{1}、{5}、{1、2、1 }および{1、3、1}。したがって、合計数は9です。

入力 − int arr [] ={2、5、5、2、1}

出力 −要素を再配置してパリンドロームを形成できるサブアレイの数は− 8

説明 −要素を配置して回文を形成できる有効なサブ配列は、{2}、{5}、{5}、{2}、{1}、{5、2、5}、{2、5、2 }、{2、5、5、2}。したがって、合計数は8です。

以下のプログラムで使用されているアプローチは次のとおりです

• 整数要素の配列を入力し、配列のサイズを計算して、さらに処理するためにデータを関数に渡します。

• 回文のサブ配列を格納するための一時変数カウントを宣言します。

• 0から配列のサイズまでループFORを開始します

• ループ内で、long long型の変数を宣言し、それを1LL <として設定します。

• trueまたはfalseを返すブール変数内の関数を呼び出します。

• tempが0LLまたはchがTrueの場合は、カウントを1ずつ増やしてください

  。

• カウントを返す

• 結果を印刷します。

例

#include <bits/stdc++.h>
using namespace std;
bool check(long long temp){
   return !(temp & (temp - 1LL));
}
int palindromes_rearrange(int arr[], int size){
   int count = 0;
   for (int i = 0; i < size; i++){
      long long temp = 0LL;
      for (int j = i; j < size; j++){
         long long val = 1LL << arr[j];
         temp = temp ^ val;
         bool ch = check(temp);
         if (temp == 0LL || ch){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 3, 1, 4, 2, 1, 5};
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of sub-arrays whose elements can be re-arranged to form palindromes are:
"<<palindromes_rearrange(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9