Check if rearranging Array elements can form a Palindrome or not
Given a positive integer array arr of size N, the task is to check if number formed, from any arrangement of array elements, form a palindrome or not.
Examples:
Input: arr = [1, 2, 3, 1, 2]
Output: Yes
Explanation: The elements of a given array can be rearranged as 1, 2, 3, 2, 1.
Since 12321 is a palindrome, so output will be “Yes”Input: arr = [1, 2, 3, 4, 1]
Output: No
Explanation: The elements of a given array cannot be rearranged to form a palindrome within all the possible permutations. So the output will be “No”
Approach: Given problem can be solved using map to store the frequency of array elements
- Store the frequency of all array elements
- Check if frequency of each element is even
- For element whose frequency is odd, if there is only one such element, then print Yes. Else print No.
Below is the implementation of the above approach:
C++14
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; #define MAX 256 // Function to check whether elements of // an array can form a palindrome bool can_form_palindrome( int arr[], int n) { // create an empty string // to append elements of an array string str = "" ; // append each element to the string str to form // a string so that we can solve it in easy way for ( int i = 0; i < n; i++) { str += arr[i]; } // Create a freq array and initialize all // values as 0 int freq[MAX] = { 0 }; // For each character in formed string, // increment freq in the corresponding // freq array for ( int i = 0; str[i]; i++) { freq[str[i]]++; } int count = 0; // Count odd occurring characters for ( int i = 0; i < MAX; i++) { if (freq[i] & 1) { count++; } if (count > 1) { return false ; } } // Return true if odd count is 0 or 1, return true ; } // Drive code int main() { int arr[] = { 1, 2, 3, 1, 2 }; int n = sizeof (arr) / sizeof ( int ); can_form_palindrome(arr, n) ? cout << "YES" : cout << "NO" ; return 0; } |
Java
// Java implementation of the above approach import java.io.*; import java.util.Arrays; class GFG{ static int MAX = 256 ; // Function to check whether elements of // an array can form a palindrome static boolean can_form_palindrome( int []arr, int n) { // create an empty string // to append elements of an array String str = "" ; // append each element to the string str to form // a string so that we can solve it in easy way for ( int i = 0 ; i < n; i++) { str += arr[i]; } // Create a freq array and initialize all // values as 0 int freq[] = new int [MAX]; Arrays.fill(freq, 0 ); // For each character in formed string, // increment freq in the corresponding // freq array for ( int i = 0 ; i<str.length(); i++) { freq[str.charAt(i)]++; } int count = 0 ; // Count odd occurring characters for ( int i = 0 ; i < MAX; i++) { if ((freq[i] & 1 )!= 0 ) { count++; } if (count > 1 ) { return false ; } } // Return true if odd count is 0 or 1, return true ; } // Drive code public static void main (String[] args) { int []arr = { 1 , 2 , 3 , 1 , 2 }; int n = arr.length; if (can_form_palindrome(arr, n)) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed by shivanisinghss2110 |
Python3
# python implementation of the above approach # Function to check whether elements of # an array can form a palindrome def can_form_palindrome(arr, n): MAX = 256 # create an empty string # to append elements of an array s = "" # append each element to the string str to form # a string so that we can solve it in easy way for i in range (n) : s = s + str (arr[i]) # Create a freq array and initialize all # values as 0 freq = [ 0 ] * MAX # For each character in formed string, # increment freq in the corresponding # freq array for i in range (N) : freq[arr[i]] = freq[arr[i]] + 1 count = 0 # Count odd occurring characters for i in range ( MAX ) : if (freq[i] & 1 ) : count = count + 1 if (count > 1 ) : return False # Return true if odd count is 0 or 1, return True # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 1 , 2 ] N = len (arr) # Function Call if (can_form_palindrome(arr, N)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by anudeep23042002 |
C#
// C# implementation of the above approach using System; using System.Collections.Generic; class GFG{ static int MAX = 256; // Function to check whether elements of // an array can form a palindrome static bool can_form_palindrome( int []arr, int n) { // create an empty string // to append elements of an array string str = "" ; // append each element to the string str to form // a string so that we can solve it in easy way for ( int i = 0; i < n; i++) { str += arr[i]; } // Create a freq array and initialize all // values as 0 int []freq = new int [MAX]; Array.Clear(freq,0,MAX); // For each character in formed string, // increment freq in the corresponding // freq array for ( int i = 0; i<str.Length; i++) { freq[str[i]]++; } int count = 0; // Count odd occurring characters for ( int i = 0; i < MAX; i++) { if ((freq[i] & 1)!=0) { count++; } if (count > 1) { return false ; } } // Return true if odd count is 0 or 1, return true ; } // Drive code public static void Main() { int []arr = { 1, 2, 3, 1, 2 }; int n = arr.Length; if (can_form_palindrome(arr, n)) Console.Write( "YES" ); else Console.Write( "NO" ); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach let MAX = 256 // Function to check whether elements of // an array can form a palindrome function can_form_palindrome(arr, n) { // create an empty string // to append elements of an array let str = "" ; // append each element to the string str to form // a string so that we can solve it in easy way for (let i = 0; i < n; i++) { str += toString(arr[i]); } // Create a freq array and initialize all // values as 0 let freq = new Array(n).fill(0); // For each character in formed string, // increment freq in the corresponding // freq array for (let i = 0; i < str.length; i++) { freq[str.charCodeAt(i)]++; } let count = 0; // Count odd occurring characters for (let i = 0; i < MAX; i++) { if (freq[i] & 1) { count++; } if (count > 1) { return false ; } } // Return true if odd count is 0 or 1, return true ; } // Drive code let arr = [1, 2, 3, 1, 2]; let n = arr.length; can_form_palindrome(arr, n) ? document.write( "YES" ) : document.write( "NO" ); // This code is contributed by Potta Lokesh </script> |
Output
YES
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us