Check if a symmetric plus is possible from the elements of the given array
Given an array arr[] of N elements, the task is to check whether asymmetric plus is possible with the elements of the given array.
A square symmetric plus is of the form:
Z Y Z Y X Y Z Y Z
Note that all the elements of the array must be used in forming the square.
Examples:
Input: arr[] = {1, 2, 1, 1, 1} Output: Yes 1 1 2 1 1 Input: arr[] = {1, 1, 1, 1, 2, 2, 2, 3, 2} Output: Yes 1 2 1 2 3 2 1 2 1 Input: arr[] = {1, 1, 1, 4, 2, 2, 2, 3, 2} Output: No
Approach: In order to form an asymmetric plus, the frequency of all the elements of the array must be a multiple of 4 and there has to be an element whose frequency gives 1 when modulo with 4.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function that return true if // a symmetric is possible with // the elements of the array bool isPlusPossible( int arr[], int n) { // Map to store the frequency // of the array elements unordered_map< int , int > mp; // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) mp[arr[i]]++; bool foundModOne = false ; // For every unique element for ( auto x : mp) { int element = x.first; int frequency = x.second; if (frequency % 4 == 0) continue ; if (frequency % 4 == 1) { // Element has already been found if (foundModOne) return false ; foundModOne = true ; } // The frequency of the element // something other than 0 and 1 else return false ; } } // Driver code int main() { int arr[] = { 1, 1, 1, 1, 2, 2, 2, 3, 2 }; int n = sizeof (arr) / sizeof (arr[0]); if (isPlusPossible(arr, n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function that return true if // a symmetric is possible with // the elements of the array static boolean isPlusPossible( int arr[], int n) { // Map to store the frequency // of the array elements HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Traverse through array elements and // count frequencies for ( int i = 0 ; i < n; i++) { if (mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1 ); } else { mp.put(arr[i], 1 ); } } boolean foundModOne = false ; // For every unique element for (Map.Entry<Integer,Integer> x : mp.entrySet()) { int element = x.getKey(); int frequency = x.getValue(); if (frequency % 4 == 0 ) continue ; if (frequency % 4 == 1 ) { // Element has already been found if (foundModOne) return false ; foundModOne = true ; } // The frequency of the element // something other than 0 and 1 else return false ; } return true ; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 2 }; int n = arr.length; if (isPlusPossible(arr, n)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach # Function that return true if # a symmetric is possible with # the elements of the array def isPlusPossible(arr, n): # Map to store the frequency # of the array elements mp = dict () # Traverse through array elements and # count frequencies for i in range (n): mp[arr[i]] = mp.get(arr[i], 0 ) + 1 foundModOne = False # For every unique element for x in mp: element = x frequency = mp[x] if (frequency % 4 = = 0 ): continue if (frequency % 4 = = 1 ): # Element has already been found if (foundModOne = = True ): return False foundModOne = True # The frequency of the element # something other than 0 and 1 else : return False return True # Driver code arr = [ 1 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 2 ] n = len (arr) if (isPlusPossible(arr, n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that return true if // a symmetric is possible with // the elements of the array static bool isPlusPossible( int []arr, int n) { // Map to store the frequency // of the array elements Dictionary< int , int > mp = new Dictionary< int , int >(); // Traverse through array elements and // count frequencies for ( int i = 0; i < n; i++) { if (mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } bool foundModOne = false ; // For every unique element foreach (KeyValuePair< int , int > x in mp) { int element = x.Key; int frequency = x.Value; if (frequency % 4 == 0) continue ; if (frequency % 4 == 1) { // Element has already been found if (foundModOne) return false ; foundModOne = true ; } // The frequency of the element // something other than 0 and 1 else return false ; } return true ; } // Driver code public static void Main(String[] args) { int []arr = { 1, 1, 1, 1, 2, 2, 2, 3, 2 }; int n = arr.Length; if (isPlusPossible(arr, n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function that return true if // a symmetric is possible with // the elements of the array function isPlusPossible(arr, n) { // Map to store the frequency // of the array elements var mp = new Map(); // Traverse through array elements and // count frequencies for ( var i = 0; i < n; i++) { if (mp.has(arr[i])) mp.set(arr[i], mp.get(arr[i])+1) else mp.set(arr[i], 1) } var foundModOne = false ; var ans = true ; // For every unique element mp.forEach((value, key) => { var element = key; var frequency = value; if (frequency % 4 != 0) { if (frequency % 4 == 1) { // Element has already been found if (foundModOne) ans = false foundModOne = true ; } // The frequency of the element // something other than 0 and 1 else ans = false } }); return ans; } // Driver code var arr = [1, 1, 1, 1, 2, 2, 2, 3, 2]; var n = arr.length; if (isPlusPossible(arr, n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output:
Yes
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us