Dada una array arr[] de tamaño N , la tarea es reorganizar los elementos de la array de modo que para cada índice i (1 <= i <= N – 1), el producto de arr[i] y arr[i – 1] es múltiplo de 4.
Ejemplo:
Entrada: arr[] = {1, 10, 100}
Salida: 1, 100, 10
Explicación:
1 * 100 es divisible por 4
100 * 10 es divisible por 4Entrada: arr[] = {2, 7, 1, 8, 2, 8}
Salida: 7, 8, 1, 8, 2, 2
Enfoque ingenuo:
el enfoque más simple para resolver el problema es generar todas las permutaciones posibles de la array y, para cada permutación, verificar si el producto de cada dos elementos consecutivos es un múltiplo de 4 o no.
Complejidad temporal: O(N^2 * N!)
Espacio auxiliar: O(N!)
Enfoque eficiente:
siga los pasos a continuación para optimizar el enfoque anterior:
- Inicialice las siguientes tres variables:
- impar = Número de elementos impares .
- cuatro = Número de elementos divisibles por 4 .
- non_four = Número de elementos pares no divisibles por 4 .
- Considere los siguientes dos casos:
- Caso 1: non_four = 0
En este caso, no hay elementos pares que no sean divisibles por 4.- La forma óptima es colocar primero los elementos «impares» primero en la array en posiciones alternas.
- Llene las vacantes con los elementos pares.
- Caso 1: non_four = 0
Ilustración
arr[] = {1, 1, 1, 4, 4}
Paso 0: cuatro = 2, impar = 3
Paso 1: {1 _ 1 _ 1}
Paso 2: {1 4 1 4 1}
- Por lo tanto, para que el enfoque sea matemáticamente posible, la diferencia entre el recuento de elementos pares e impares no debe exceder de 1.
- Caso 2: no_cuatro > 0
En este caso, incluso los elementos que no son divisibles por 4 existen en la array.
- Siga exactamente la misma estrategia que se muestra arriba colocando los elementos divisibles por 4 en posiciones alternas seguidos de elementos impares en las vacantes.
- Luego, coloque todos los elementos pares restantes al final de la array. Esto se debe a que el producto de dos números pares siempre es divisible por 4. Por lo tanto, colocar los elementos pares hacia el final de la array garantiza que el producto de los elementos consecutivos entre ellos sea divisible por 4.
Ilustración:
arr[] = {2, 7, 1, 8, 2, 8}
Paso 1: cuatro = 2, non_four = 2, impar = 2
Paso 2: {_ 8 _ 8}
Paso 3: {1 8 7 8 }
Paso 4: {1 8 7 8 2 2}
- Para que esto sea posible matemáticamente, cuatro >= impares .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to rearray array
// elements such that the product
// of every two consecutive
// elements is a multiple of 4
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange array
// elements such that the every
// two consecutive elements is
// a multiple of 4
void Permute(vector<int>& arr,
int n)
{
int odd = 0, four = 0;
int non_four = 0;
vector<int> ODD, FOUR,
NON_FOUR;
for (auto x : arr) {
// If element is odd
if (x & 1) {
odd++;
// Odd
ODD.push_back(x);
}
// If element is divisible
// by 4
else if (x % 4 == 0) {
four++;
// Divisible by 4
FOUR.push_back(x);
}
// If element is not
// divisible by 4
else {
non_four++;
// Even but not divisible
// by 4
NON_FOUR.push_back(x);
}
}
// Condition for rearrangement
// to be possible
if (non_four == 0
&& four >= odd - 1) {
int x = ODD.size();
int y = FOUR.size();
int i;
// Print ODD[i] and FOUR[i]
// consecutively
for (i = 0; i < x; i++) {
cout << ODD[i] << " ";
if (i < y)
cout << FOUR[i] << " ";
}
// Print the remaining
// FOUR[i], if any
while (i < y)
cout << FOUR[i] << " ";
cout << endl;
}
// Condition for rearrangement
// to be possible
else if (non_four > 0
and four >= odd) {
int x = ODD.size();
int y = FOUR.size();
int i;
// Print ODD[i] and FOUR[i]
// consecutively
for (i = 0; i < x; i++) {
cout << ODD[i] << " ";
if (i < y)
cout << FOUR[i] << " ";
}
// Print the remaining
// FOUR[i], if any
while (i < y)
cout << FOUR[i] << " ";
// Print the NON_FOUR[i]
// elements at the end
for (int j = 0;
j < (int)NON_FOUR.size();
j++)
cout << NON_FOUR[j] << " ";
cout << endl;
}
else
// No possible configuration
cout << "Not Possible" << endl;
}
// Driver Code
signed main()
{
vector<int> arr = { 2, 7, 1,
8, 2, 8 };
int N = sizeof(arr) / sizeof(arr);
Permute(arr, N);
return 0;
}
Java
// Java program to rearray array
// elements such that the product
// of every two consecutive
// elements is a multiple of
import java.io.*;
import java.util.*;
class GFG{
// Function to rearrange array
// elements such that the every
// two consecutive elements is
// a multiple of 4
public static void Permute(Vector<Integer> arr, int n)
{
int odd = 0, four = 0;
int non_four = 0;
Vector<Integer> ODD = new Vector<Integer>();
Vector<Integer> FOUR = new Vector<Integer>(n);
Vector<Integer> NON_FOUR = new Vector<Integer>(n);
for(int x : arr)
{
// If element is odd
if (x % 2 != 0)
{
odd++;
// Odd
ODD.add(x);
}
// If element is divisible
// by 4
else if (x % 4 == 0)
{
four++;
// Divisible by 4
FOUR.add(x);
}
// If element is not
// divisible by 4
else
{
non_four++;
// Even but not divisible
// by 4
NON_FOUR.add(x);
}
}
// Condition for rearrangement
// to be possible
if (non_four == 0 && four >= odd - 1)
{
int x = ODD.size();
int y = FOUR.size();
int i;
// Print ODD.get(i) and FOUR.get(i)
// consecutively
for(i = 0; i < x; i++)
{
System.out.print(ODD.get(i) + " ");
if (i < y)
System.out.print(FOUR.get(i) + " ");
}
// Print the remaining
// FOUR.get(i), if any
while (i < y)
System.out.print(FOUR.get(i) + " ");
System.out.println();
}
// Condition for rearrangement
// to be possible
else if (non_four > 0 && four >= odd)
{
int x = ODD.size();
int y = FOUR.size();
int i;
// Print ODD.get(i) and FOUR.get(i)
// consecutively
for(i = 0; i < x; i++)
{
System.out.print(ODD.get(i) + " ");
if (i < y)
System.out.print(FOUR.get(i) + " ");
}
// Print the remaining
// FOUR.get(i), if any
while (i < y)
System.out.print(FOUR.get(i) + " ");
// Print the NON_FOUR.get(i)
// elements at the end
for(int j = 0; j < (int)NON_FOUR.size(); j++)
System.out.print(NON_FOUR.get(j) + " ");
System.out.println();
}
else
// No possible configuration
System.out.println("Not Possible");
}
// Driver Code
public static void main(String[] args)
{
Vector<Integer> arr = new Vector<Integer>();
arr.add(2);
arr.add(7);
arr.add(1);
arr.add(8);
arr.add(2);
arr.add(8);
Permute(arr, arr.size());
}
}
// This code is contributed by grand_master
Python3
# Python3 program to rearray array
# elements such that the product
# of every two consecutive
# elements is a multiple of 4
# Function to rearrange array
# elements such that the every
# two consecutive elements is
# a multiple of 4
def Permute(arr, n):
odd = 0
four = 0
non_four = 0
ODD, FOUR, NON_FOUR = [], [], []
for x in arr:
# If element is odd
if (x & 1):
odd += 1
# Odd
ODD.append(x)
# If element is divisible
# by 4
elif (x % 4 == 0):
four += 1
# Divisible by 4
FOUR.append(x)
# If element is not
# divisible by 4
else:
non_four += 1
# Even but not divisible
# by 4
NON_FOUR.append(x)
# Condition for rearrangement
# to be possible
if (non_four == 0 and four >= odd - 1):
x = len(ODD)
y = len(FOUR)
i = 0
# Print ODD[i] and FOUR[i]
# consecutively
while i < x:
print(ODD[i], end = " ")
if (i < y):
print(FOUR[i], end = " ")
# Print the remaining
# FOUR[i], if any
while (i < y):
print(FOUR[i], end = " ")
i += 1
print()
# Condition for rearrangement
# to be possible
elif (non_four > 0 and four >= odd):
x = len(ODD)
y = len(FOUR)
i = 0
# Print ODD[i] and FOUR[i]
# consecutively
while i < x:
print(ODD[i], end = " ")
if (i < y):
print(FOUR[i], end = " ")
i += 1
# Print the remaining
# FOUR[i], if any
while (i < y):
print(FOUR[i], end = " ")
i += 1
# Print the NON_FOUR[i]
# elements at the end
for j in NON_FOUR:
print(j, end = " ")
else:
# No possible configuration
print("Not Possible")
# Driver Code
if __name__ == '__main__':
arr = [ 2, 7, 1, 8, 2, 8 ]
N = len(arr)
Permute(arr, N)
# This code is contributed by mohit kumar 29
C#
// C# program to rearray array
// elements such that the product
// of every two consecutive
// elements is a multiple of
using System;
using System.Collections.Generic;
class GFG{
// Function to rearrange array
// elements such that the every
// two consecutive elements is
// a multiple of 4
public static void Permute(List<int> arr,
int n)
{
int odd = 0, four = 0;
int non_four = 0;
List<int> ODD =
new List<int>();
List<int> FOUR =
new List<int>(n);
List<int> NON_FOUR =
new List<int>(n);
foreach(int x in arr)
{
// If element is odd
if (x % 2 != 0)
{
odd++;
// Odd
ODD.Add(x);
}
// If element is divisible
// by 4
else if (x % 4 == 0)
{
four++;
// Divisible by 4
FOUR.Add(x);
}
// If element is not
// divisible by 4
else
{
non_four++;
// Even but not divisible
// by 4
NON_FOUR.Add(x);
}
}
// Condition for rearrangement
// to be possible
if (non_four == 0 &&
four >= odd - 1)
{
int x = ODD.Count;
int y = FOUR.Count;
int i;
// Print ODD[i] and FOUR[i]
// consecutively
for(i = 0; i < x; i++)
{
Console.Write(ODD[i] + " ");
if (i < y)
Console.Write(FOUR[i] + " ");
}
// Print the remaining
// FOUR[i], if any
while (i < y)
Console.Write(FOUR[i] + " ");
Console.WriteLine();
}
// Condition for rearrangement
// to be possible
else if (non_four > 0 &&
four >= odd)
{
int x = ODD.Count;
int y = FOUR.Count;
int i;
// Print ODD[i] and FOUR[i]
// consecutively
for(i = 0; i < x; i++)
{
Console.Write(ODD[i] + " ");
if (i < y)
Console.Write(FOUR[i] + " ");
}
// Print the remaining
// FOUR[i], if any
while (i < y)
Console.Write(FOUR[i] + " ");
// Print the NON_FOUR[i]
// elements at the end
for(int j = 0;
j < (int)NON_FOUR.Count; j++)
Console.Write(NON_FOUR[j] + " ");
Console.WriteLine();
}
else
// No possible configuration
Console.WriteLine("Not Possible");
}
// Driver Code
public static void Main(String[] args)
{
List<int> arr = new List<int>();
arr.Add(2);
arr.Add(7);
arr.Add(1);
arr.Add(8);
arr.Add(2);
arr.Add(8);
Permute(arr, arr.Count);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to rearray array
// elements such that the product
// of every two consecutive
// elements is a multiple of
// Function to rearrange array
// elements such that the every
// two consecutive elements is
// a multiple of 4
function Permute(arr,n)
{
let odd = 0, four = 0;
let non_four = 0;
let ODD = [];
let FOUR = [];
let NON_FOUR = [];
for(let x = 0; x < arr.length; x++)
{
// If element is odd
if (arr[x] % 2 != 0)
{
odd++;
// Odd
ODD.push(arr[x]);
}
// If element is divisible
// by 4
else if (arr[x] % 4 == 0)
{
four++;
// Divisible by 4
FOUR.push(arr[x]);
}
// If element is not
// divisible by 4
else
{
non_four++;
// Even but not divisible
// by 4
NON_FOUR.push(arr[x]);
}
}
// Condition for rearrangement
// to be possible
if (non_four == 0 && four >= odd - 1)
{
let x = ODD.length;
let y = FOUR.length;
let i;
// Print ODD.get(i) and FOUR.get(i)
// consecutively
for(i = 0; i < x; i++)
{
document.write(ODD[i] + " ");
if (i < y)
document.write(FOUR[i] + " ");
}
// Print the remaining
// FOUR.get(i), if any
while (i < y)
document.write(FOUR[i] + " ");
document.write("<br>");
}
// Condition for rearrangement
// to be possible
else if (non_four > 0 && four >= odd)
{
let x = ODD.length;
let y = FOUR.length;
let i;
// Print ODD.get(i) and FOUR.get(i)
// consecutively
for(i = 0; i < x; i++)
{
document.write(ODD[i] + " ");
if (i < y)
document.write(FOUR[i] + " ");
}
// Print the remaining
// FOUR.get(i), if any
while (i < y)
document.write(FOUR[i] + " ");
// Print the NON_FOUR.get(i)
// elements at the end
for(let j = 0; j < NON_FOUR.length; j++)
document.write(NON_FOUR[j] + " ");
document.write("<br>");
}
else
// No possible configuration
document.write("Not Possible<br>");
}
// Driver Code
let arr=[2,7,1,8,2,8]
Permute(arr, arr.length);
// This code is contributed by patel2127
</script>
Producción:
7 8 1 8 2 2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA