Chúng ta được cung cấp một mảng các phần tử nguyên và nhiệm vụ là tính số mảng con có thể được hình thành từ mảng đã cho sao cho các phần tử của nó có thể tạo thành một palindrome hợp lệ. Palindromes là các chuỗi được sắp xếp tương tự nhau từ đầu và cuối.
Đầu vào - int arr [] ={3, 3, 1, 4, 2, 1, 5}
Đầu ra - Số mảng con có các phần tử có thể được sắp xếp lại để tạo thành các mảng là - 9
Giải thích - Các mảng con hợp lệ có các phần tử có thể được sắp xếp để tạo thành một palindrome là {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1, 2, 1 } và {1, 3, 1}. Vì vậy, tổng số là 9.
Đầu vào - int arr [] ={2, 5, 5, 2, 1}
Đầu ra - Số lượng mảng con có các phần tử có thể được sắp xếp lại để tạo thành palindromes là - 8
Giải thích - Các mảng con hợp lệ có các phần tử có thể được sắp xếp để tạo thành một palindrome là {2}, {5}, {5}, {2}, {1}, {5, 2, 5}, {2, 5, 2 }, {2, 5, 5, 2}. Vì vậy, tổng số là 8.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Nhập một mảng các phần tử số nguyên và tính toán kích thước của một mảng và chuyển dữ liệu vào hàm để xử lý thêm.
-
Khai báo số lượng biến tạm thời để lưu trữ các mảng con của palindrome.
-
Bắt đầu vòng lặp FOR từ 0 cho đến hết kích thước của một mảng
-
Bên trong vòng lặp, khai báo một biến có kiểu long long và đặt nó là 1LL <
-
Gọi một hàm bên trong biến boolean sẽ trả về true hoặc false.
-
Kiểm tra IF temp là 0LL hoặc ch là True sau đó tăng số đếm lên 1
-
Trả lại số lượng
-
In kết quả.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9