C++에서 회문을 형성하기 위해 요소를 재배열할 수 있는 하위 배열의 수

정수 요소의 배열이 주어지고 그 요소가 유효한 회문을 형성할 수 있도록 주어진 배열에서 구성할 수 있는 하위 배열의 수를 계산하는 작업입니다. 회문은 시작과 끝이 비슷하게 배열된 시퀀스입니다.

입력 - 정수 arr[] ={ 3, 3, 1, 4, 2, 1, 5}

출력 − 회문을 형성하기 위해 요소를 재배열할 수 있는 하위 배열의 수는 − 9

설명 − 요소를 배열하여 회문을 형성할 수 있는 유효한 하위 배열은 {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1, 2, 1입니다. } 및 {1, 3, 1}. 따라서 총 개수는 9입니다.

입력 - 정수 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