Dada una array arr[] de N elementos, la tarea es comprobar si es posible un plus asimétrico con los elementos de la array dada.
Un cuadrado simétrico más es de la forma:
Z
Y
Z Y X Y Z
Y
Z
Tenga en cuenta que todos los elementos de la array deben usarse para formar el cuadrado.
Ejemplos:
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
Planteamiento: Para formar un más asimétrico, la frecuencia de todos los elementos del arreglo debe ser múltiplo de 4 y tiene que haber un elemento cuya frecuencia dé 1 cuando módulo con 4.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(n)