An array [b1,b2,…,bm] is a palindrome, if bi=bm+1−i for each i from 1 to m. Empty array is also a palindrome. An array is called kalindrome, if the following condition holds: It's possible to select some integer x and delete some of the elements of the array equal to x, so that the remaining array (after gluing together the remaining parts) is a palindrome. Note that you don't have to delete all elements equal to x, and you don't have to delete at least one element equal to x. For example : [1,2,1] is kalindrome because you can simply not delete a single element. [3,1,2,3,1] is kalindrome because you can choose x=3 and delete both elements equal to 3, obtaining array [1,2,1], which is a palindrome. [1,2,3] is not kalindrome. You are given an array [a1,a2,…,an]. Determine if a is kalindrome or not.
#include <iostream>
#include <bits/stdc++.h>
#define loop for(int i=0; i<n; i++)
using namespace std;
int remove(int numbers[], int n, int value)
{
int o = 0;
// for(int i=0; i<n; i++)
loop
{
if (numbers[i] != value)
{
numbers[o++] = numbers[i];
}
}
return o;
}
int mostFrequent(int arr[], int n)
{
// Sort the array
sort(arr, arr + n);
// find the max frequency using linear traversal
int max_count = 1, res = arr[0], curr_count = 1;
// for (int i = 1; i < n; i++)
loop
{
if (arr[i] == arr[i - 1])
curr_count++;
else
{
if (curr_count > max_count)
{
max_count = curr_count;
res = arr[i - 1];
}
curr_count = 1;
}
}
// If last element is most frequent
if (curr_count > max_count)
{
max_count = curr_count;
res = arr[n - 1];
}
return res;
}
int palindrome(int arr[], int n)
{
// Initialise flag to zero.
int flag = 0, r;
// Loop till array size n/2.
for (int i = 0; i <= n / 2 && n != 0; i++)
{
// Check if first and last element are different
// Then set flag to 1.
if (arr[i] != arr[n - i - 1])
{
flag = 1;
break;
}
}
// If flag is set then print Not Palindrome
// else print Palindrome.
if (flag == 1)
{
r = 0;
}
else
{
r = 1;
}
return r;
}
int main()
{
int t;
cin >> t;
while (t--)
{
int arr[50], n, p;
cin >> n;
// for (int i = 0; i < n; i++)
loop
{
cin >> arr[i];
}
p = palindrome(arr, n);
// cout << p;
if (p == 1)
{
cout << "YES" << endl;
}
else
{
int u = mostFrequent(arr, n);
// cout << u;
int r = remove(arr, n, u);
p = palindrome(arr, r);
if (p == 1)
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}
}
