Given an array arr[] of size N, the task is to check if any subarray from the given array can be made a palindrome by replacing less than half of its elements (i.e. floor[length/2]) by any other element of the subarray.
Examples:
Input: arr[] = {2, 7, 4, 6, 7, 8}
Output: Yes
Explanation: Among all subarrays of this array, subarray {7, 4, 6, 7} requires only 1 operation to make it a palindrome i.e. replace arr[3] by 4 or arr[4] by 6, which is less than floor(4/2) ( = 2).Input: arr[] = {3, 7, 19, 6}
Output: No
Naive Approach: The simplest approach to solve this problem is to generate all subarrays of the given array and for each subarray, check if the number of replacements required to make that subarray a palindrome is less than floor(length of subarray / 2).
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
If the array arr[] contains duplicate elements, then it is always possible to choose a subarray from initial occurrence to the next occurrence of that element. This subarray will require less than floor(length/2) operations as first and last element of subarray is already equal.
Follow the steps below to solve the problem:
- Initialize a Map for storing the frequencies of each array element.
- Iterate over all array elements and count frequency of each array element and insert it into the Map.
- Check if frequency of any array element is found to be greater than 1.. If found to be true, print “Yes”. Otherwise, print “No”.
Below is the implementation of this approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A Utility Function to check if a subarray// can be palindromic by replacing less than// half of the elements present in itbool isConsistingSubarrayUtil(int arr[], int n){ // Stores frequency of array elements map<int, int> mp; // Traverse the array for (int i = 0; i < n; ++i) { // Update frequency of // each array element mp[arr[i]]++; } // Iterator over the Map map<int, int>::iterator it; for (it = mp.begin(); it != mp.end(); ++it) { // If frequency of any element exceeds 1 if (it->second > 1) { return true; } } // If no repetition is found return false;}// Function to check and print if any subarray// can be made palindromic by replacing less// than half of its elementsvoid isConsistingSubarray(int arr[], int N){ if (isConsistingSubarrayUtil(arr, N)) { cout << "Yes" << endl; } else { cout << "No" << endl; }}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 2, 3, 4, 5, 1 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Function Call isConsistingSubarray(arr, N); return 0;} |
Java
// Java program for the above approach import java.util.*; class GFG{ // A Utility Function to check if a subarray// can be palindromic by replacing less than// half of the elements present in itstatic boolean isConsistingSubarrayUtil(int arr[], int n){ // Stores frequency of array elements TreeMap<Integer, Integer> mp = new TreeMap<Integer, Integer>(); // Traverse the array for(int i = 0; i < n; ++i) { // Update frequency of // each array element mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1); } for(Map.Entry<Integer, Integer> it : mp.entrySet()) { // If frequency of any element exceeds 1 if (it.getValue() > 1) { return true; } } // If no repetition is found return false;} // Function to check and print if any subarray// can be made palindromic by replacing less// than half of its elementsstatic void isConsistingSubarray(int arr[], int N){ if (isConsistingSubarrayUtil(arr, N)) { System.out.println("Yes"); } else { System.out.println("No"); }} // Driver Codepublic static void main(String args[]){ // Given array arr[] int arr[] = { 1, 2, 3, 4, 5, 1 }; // Size of array int N = arr.length; // Function Call isConsistingSubarray(arr, N);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program for the above approach# A Utility Function to check if a subarray# can be palindromic by replacing less than# half of the elements present in itdef isConsistingSubarrayUtil(arr, n) : # Stores frequency of array elements mp = {}; # Traverse the array for i in range(n) : # Update frequency of # each array element if arr[i] in mp : mp[arr[i]] += 1; else : mp[arr[i]] = 1; # Iterator over the Map for it in mp : # If frequency of any element exceeds 1 if (mp[it] > 1) : return True; # If no repetition is found return False;# Function to check and print if any subarray# can be made palindromic by replacing less# than half of its elementsdef isConsistingSubarray(arr, N) : if (isConsistingSubarrayUtil(arr, N)) : print("Yes"); else : print("No");# Driver Codeif __name__ == "__main__" : # Given array arr[] arr = [ 1, 2, 3, 4, 5, 1 ]; # Size of array N = len(arr); # Function Call isConsistingSubarray(arr, N); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic; using System.Linq; class GFG{ // A Utility Function to check if a subarray// can be palindromic by replacing less than// half of the elements present in itstatic bool isConsistingSubarrayUtil(int[] arr, int n){ // Stores frequency of array elements Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < n; ++i) { // Update frequency of // each array element if (mp.ContainsKey(arr[i]) == true) mp[arr[i]] += 1; else mp[arr[i]] = 1; } var val = mp.Keys.ToList(); foreach(var key in val) { // If frequency of any element exceeds 1 if (mp[key] > 1) { return true; } } // If no repetition is found return false;} // Function to check and print if any subarray// can be made palindromic by replacing less// than half of its elementsstatic void isConsistingSubarray(int[] arr, int N){ if (isConsistingSubarrayUtil(arr, N)) { Console.Write("Yes"); } else { Console.Write("No"); }} // Driver Codepublic static void Main(){ // Given array arr[] int[] arr = { 1, 2, 3, 4, 5, 1 }; // Size of array int N = arr.Length; // Function Call isConsistingSubarray(arr, N);}}// This code is contributed by sanjoy62 |
Javascript
<script>// Javascript program for the above approach// A Utility Function to check if a subarray// can be palindromic by replacing less than// half of the elements present in itfunction isConsistingSubarrayUtil(arr, n){ // Stores frequency of array elements var mp = new Map(); // Traverse the array for (var i = 0; i < n; ++i) { // Update frequency of // each array element if(mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i])+1); } else { mp.set(arr[i], 1); } } var ans = false; // Iterator over the Map mp.forEach((value, key) => { // If frequency of any element exceeds 1 if (value > 1) { ans = true; } }); if(ans) return true; // If no repetition is found return false;}// Function to check and print if any subarray// can be made palindromic by replacing less// than half of its elementsfunction isConsistingSubarray(arr, N){ if (isConsistingSubarrayUtil(arr, N)) { document.write( "Yes"); } else { document.write( "No" ); }}// Driver Code// Given array arr[]var arr = [1, 2, 3, 4, 5, 1];// Size of arrayvar N = arr.length;// Function CallisConsistingSubarray(arr, N);</script> |
Output:
Yes
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
