นับจำนวนซับอาเรย์ที่จัดเรียงใหม่ได้เป็นพาลินโดรมใน 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

แนวทางที่ใช้ในโปรแกรม

• รับอาเรย์จำนวนเต็มและคำนวณขนาด ส่งไปฟังก์ชันประมวลผล
• ประกาศตัวแปรชั่วคราว count เก็บซับอาเรย์พาลินโดรม
• ลูป FOR จาก 0 ถึงขนาดอาเรย์
• ในลูป ประกาศตัวแปร long long กำหนดเป็น 1LL << arr[j] และ temp = temp ^ val
• เรียกฟังก์ชันในตัวแปรบูลีนที่คืนค่า true หรือ false
• ตรวจสอบถ้า temp == 0LL หรือ ch == true เพิ่ม count 1
• คืนค่า count
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด C++

#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