Dada una array arr[] que consiste en N enteros positivos, la tarea es encontrar cualquier permutación de la array dada tal que el producto de los elementos adyacentes sea par. Imprime cualquier permutación o -1 si no es posible.
Ejemplo:
Entrada: arr[] = {6,7,9,8,10,11}
Salida: 8 9 10 7 6 11
Explicación:
Producto de elementos adyacentes =>
8 x 9 = 72 (par)
9 x 10 = 90 (par )
10 x 7 = 70 (par)
7 x 6 = 42 (par)
6 x 11 = 66 (par)Entrada: arr[] = {3,2,5,7,1,4,9}
Salida : -1
Explicación: No hay arreglos posibles de elementos tales que el producto de elementos adyacentes sea igual.
Enfoque ingenuo: el enfoque más simple para resolver este problema es probar todos los arreglos posibles de los elementos y verificar que la condición sea verdadera.
Complejidad de tiempo: O(N*N!) donde N es el número de elementos en la array. O(N!) es el tiempo necesario para crear todas las permutaciones de la array dada y O(N) es el tiempo necesario para comprobar si la permutación actual es la necesaria o no.
Espacio auxiliar: O(N) para almacenar la permutación cada vez.
Enfoque eficiente: la solución se puede encontrar usando observaciones simples. Si hay varios elementos pares e impares en la array, una disposición óptima de los elementos adyacentes puede ser cualquiera de los siguientes casos para que el producto sea par:
{Impar, Par}
{Par, Impar}
{Par, Par}Tenga en cuenta que la disposición {Impar, Impar} de cualquier elemento adyacente dará como resultado un producto impar. Por lo tanto, este arreglo no es posible.
Las disposiciones anteriores sólo son posibles si
número_de_elementos_impares <= número_de_elementos_pares + 1 en la array.
Siga los pasos a continuación para resolver el problema.
- Tome dos vectores pares e impares para almacenar los elementos pares e impares de la array por separado.
- Si el tamaño del vector impar es mayor que el tamaño del vector par + 1 (como se explicó anteriormente), entonces la solución no es posible. Por lo tanto, imprima -1 .
- De lo contrario, primero imprima un elemento del vector impar y luego un elemento del vector par hasta que ambos vectores estén vacíos.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to Permutation of Array
// such that product of all
// adjacent elements is even
#include <bits/stdc++.h>
using namespace std;
// Function to print
// the required permutation
void printPermutation(int arr[], int n)
{
vector<int> odd, even;
// push odd elements in 'odd'
// and even elements in 'even'
for (int i = 0; i < n; i++) {
if (arr[i] % 2 == 0)
even.push_back(arr[i]);
else
odd.push_back(arr[i]);
}
int size_odd = odd.size();
int size_even = even.size();
// Check if it possible to
// arrange the elements
if (size_odd > size_even + 1)
cout << -1 << endl;
// else print the permutation
else {
int i = 0;
int j = 0;
while (i < size_odd && j < size_even) {
cout << odd[i] << " ";
++i;
cout << even[j] << " ";
++j;
}
// Print remaining odds are even.
// and even elements
while (i < size_odd) {
cout << odd[i] << " ";
++i;
}
while (j < size_even) {
cout << even[j] << " ";
}
}
}
// Driver code
int main()
{
int arr[] = { 6, 7, 9, 8, 10, 11 };
int N = sizeof(arr) / sizeof(arr[0]);
printPermutation(arr, N);
return 0;
}
Java
// Java program to permutation of array
// such that product of all adjacent
// elements is even
import java.io.*;
import java.util.*;
class GFG{
// Function to print
// the required permutation
static void printPermutation(int arr[], int n)
{
ArrayList<Integer> odd = new ArrayList<Integer>();
ArrayList<Integer> even = new ArrayList<Integer>();
// push odd elements in 'odd'
// and even elements in 'even'
for(int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
even.add(arr[i]);
else
odd.add(arr[i]);
}
int size_odd = odd.size();
int size_even = even.size();
// Check if it possible to
// arrange the elements
if (size_odd > size_even + 1)
System.out.println("-1");
// Else print the permutation
else
{
int i = 0;
int j = 0;
while (i < size_odd && j < size_even)
{
System.out.print(odd.get(i) + " ");
++i;
System.out.print(even.get(j) + " ");
++j;
}
// Print remaining odds are even.
// and even elements
while (i < size_odd)
{
System.out.print(odd.get(i) + " ");
++i;
}
while (j < size_even)
{
System.out.print(even.get(j) + " ");
}
}
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { 6, 7, 9, 8, 10, 11 };
int N = arr.length;
printPermutation(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program to Permutation of Array # such that product of all # adjacent elements is even # Function to print # the required permutation def printPermutation(arr, n): odd, even = [], [] # push odd elements in 'odd' # and even elements in 'even' for i in range(n): if(arr[i] % 2 == 0): even.append(arr[i]) else: odd.append(arr[i]) size_odd = len(odd) size_even = len(even) # Check if it possible to # arrange the elements if(size_odd > size_even + 1): print(-1) # else print the permutation else: i, j = 0, 0 while(i < size_odd and j < size_even): print(odd[i], end = " ") i += 1 print(even[j], end = " ") j += 1 # Print remaining odds are even. # and even elements while(i < size_odd): print(odd[i], end = " ") i += 1 while(j < size_even): print(even[j], end = " ") j += 1 # Driver Code arr = [ 6, 7, 9, 8, 10, 11 ] N = len(arr) # Function call printPermutation(arr, N) # This code is contributed by Shivam Singh
C#
// C# program to permutation of array
// such that product of all adjacent
// elements is even
using System;
using System.Collections.Generic;
class GFG{
// Function to print
// the required permutation
static void printPermutation(int []arr, int n)
{
List<int> odd = new List<int>();
List<int> even = new List<int>();
// push odd elements in 'odd'
// and even elements in 'even'
for(int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
even.Add(arr[i]);
else
odd.Add(arr[i]);
}
int size_odd = odd.Count;
int size_even = even.Count;
// Check if it possible to
// arrange the elements
if (size_odd > size_even + 1)
Console.WriteLine("-1");
// Else print the permutation
else
{
int i = 0;
int j = 0;
while (i < size_odd && j < size_even)
{
Console.Write(odd[i] + " ");
++i;
Console.Write(even[j] + " ");
++j;
}
// Print remaining odds are even.
// and even elements
while (i < size_odd)
{
Console.Write(odd[i] + " ");
++i;
}
while (j < size_even)
{
Console.Write(even[j] + " ");
}
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 6, 7, 9, 8, 10, 11 };
int N = arr.Length;
printPermutation(arr, N);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to permutation of array
// such that product of all adjacent
// elements is even
// Function to print
// the required permutation
function printPermutation(arr, n)
{
let odd = [];
let even = [];
// push odd elements in 'odd'
// and even elements in 'even'
for(let i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
even.push(arr[i]);
else
odd.push(arr[i]);
}
let size_odd = odd.length;
let size_even = even.length;
// Check if it possible to
// arrange the elements
if (size_odd > size_even + 1)
document.write("-1");
// Else print the permutation
else
{
let i = 0;
let j = 0;
while (i < size_odd && j < size_even)
{
document.write(odd[i] + " ");
++i;
document.write(even[j] + " ");
++j;
}
// Print remaining odds are even.
// and even elements
while (i < size_odd)
{
document.write(odd[i] + " ");
++i;
}
while (j < size_even)
{
document.write(even[j] + " ");
}
}
}
// Driver Code
let arr = [ 6, 7, 9, 8, 10, 11 ];
let N = arr.length;
printPermutation(arr, N);
</script>
7 6 9 8 11 10
Complejidad temporal: O(N) donde N es el número de elementos. Se requiere tiempo O(N) para atravesar la array dada y formar los vectores pares e impares y se requiere O(N) para imprimir la permutación.
Espacio Auxiliar: O(N) porque los elementos dados del arreglo están distribuidos entre los dos vectores.
Publicación traducida automáticamente
Artículo escrito por sri_srajit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA