Dada una array arr[] de 1 y 2 , la tarea es reorganizar la array de tal manera que la suma del prefijo de la array reorganizada tenga el número máximo de números primos. Tenga en cuenta que puede haber varias respuestas.
Ejemplos:
Entrada: arr[] = {1, 2, 1, 2, 1}
Salida: 2 1 1 1 2
La array de suma de prefijos es {2, 3, 4, 5, 7} que tiene {2, 3, 5, 7 } como números primos,
que es el máximo posible.
Entrada: arr[] = {1, 1, 2, 1, 1, 1, 2, 1, 1}
Salida: 2 1 1 1 1 1 1 1 2
Enfoque: el problema se puede resolver con dos observaciones, una es que el primer primo es 2 y todos los demás primos después de eso son números impares (Todos los números impares no son primos). Por lo tanto, simplemente llene la primera posición con 2 si hay alguno, y luego llene un número impar de unos, y luego llene los 2 restantes. Al final inserte el único 1 que queda (si el número inicial de unos fuera par).
Al hacerlo, comenzamos desde 2 y terminamos en un número impar al agregar un número impar de 1 y luego al agregarle 2, saltamos de un número impar a otro número impar que maximiza la probabilidad de números primos.
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 to print the re-arranged array
void solve(int a[], int n)
{
int ones = 0, twos = 0;
// Count the number of
// ones and twos in a[]
for (int i = 0; i < n; i++) {
// If the array element is 1
if (a[i] == 1)
ones++;
// Array element is 2
else
twos++;
}
int ind = 0;
// If it has at least one 2
// Fill up first 2
if (twos)
a[ind++] = 2;
// Decrease the cnt of
// ones if even
bool evenOnes = (ones % 2 == 0) ? true : false;
if (evenOnes)
ones -= 1;
// Fill up with odd count of ones
for (int i = 0; i < ones; i++)
a[ind++] = 1;
// Fill up with remaining twos
for (int i = 0; i < twos - 1; i++)
a[ind++] = 2;
// If even ones, then fill last position
if (evenOnes)
a[ind++] = 1;
// Print the rearranged array
for (int i = 0; i < n; i++)
cout << a[i] << " ";
}
// Driver code
int main()
{
int a[] = { 1, 2, 1, 2, 1 };
int n = sizeof(a) / sizeof(a[0]);
solve(a, n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
// Function to print the re-arranged array
static void solve(int a[], int n)
{
int ones = 0, twos = 0;
// Count the number of
// ones and twos in a[]
for (int i = 0; i < n; i++) {
// If the array element is 1
if (a[i] == 1)
ones++;
// Array element is 2
else
twos++;
}
int ind = 0;
// If it has at least one 2
// Fill up first 2
if (twos > 0)
a[ind++] = 2;
// Decrease the cnt of
// ones if even
boolean evenOnes = (ones % 2 == 0) ? true : false;
if (evenOnes)
ones -= 1;
// Fill up with odd count of ones
for (int i = 0; i < ones; i++)
a[ind++] = 1;
// Fill up with remaining twos
for (int i = 0; i < twos - 1; i++)
a[ind++] = 2;
// If even ones, then fill last position
if (evenOnes)
a[ind++] = 1;
// Print the rearranged array
for (int i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
// Driver code
public static void main(String[] args)
{
int a[] = { 1, 2, 1, 2, 1 };
int n = a.length;
solve(a, n);
}
}
// This code is contributed by ajit.
Python
# Python3 implementation of the approach # Function to print the re-arranged array def solve(a, n): ones, twos = 0, 0 # Count the number of # ones and twos in a[] for i in range(n): # If the array element is 1 if (a[i] == 1): ones+=1 # Array element is 2 else: twos+=1 ind = 0 # If it has at least one 2 # Fill up first 2 if (twos): a[ind] = 2 ind+=1 # Decrease the cnt of # ones if even if ones % 2 == 0: evenOnes = True else: evenOnes = False if (evenOnes): ones -= 1 # Fill up with odd count of ones for i in range(ones): a[ind] = 1 ind += 1 # Fill up with remaining twos for i in range(twos-1): a[ind] = 2 ind += 1 # If even ones, then fill last position if (evenOnes): a[ind] = 1 ind += 1 # Print the rearranged array for i in range(n): print(a[i],end = " ") # Driver code a = [1, 2, 1, 2, 1] n = len(a) solve(a, n) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the re-arranged array
static void solve(int []a, int n)
{
int ones = 0, twos = 0;
// Count the number of
// ones and twos in a[]
for (int i = 0; i < n; i++)
{
// If the array element is 1
if (a[i] == 1)
ones++;
// Array element is 2
else
twos++;
}
int ind = 0;
// If it has at least one 2
// Fill up first 2
if (twos > 0)
a[ind++] = 2;
// Decrease the cnt of
// ones if even
bool evenOnes = (ones % 2 == 0) ? true : false;
if (evenOnes)
ones -= 1;
// Fill up with odd count of ones
for (int i = 0; i < ones; i++)
a[ind++] = 1;
// Fill up with remaining twos
for (int i = 0; i < twos - 1; i++)
a[ind++] = 2;
// If even ones, then fill last position
if (evenOnes)
a[ind++] = 1;
// Print the rearranged array
for (int i = 0; i < n; i++)
Console.Write(a[i] + " ");
}
// Driver code
static public void Main ()
{
int []a = { 1, 2, 1, 2, 1 };
int n = a.Length;
solve(a, n);
}
}
// This code is contributed by Tushil.
PHP
<?php
// PHP implementation of the approach
// Function to print the re-arranged array
function solve($a, $n)
{
$ones = 0; $twos = 0;
// Count the number of
// ones and twos in a[]
for ($i = 0; $i < $n; $i++)
{
// If the array element is 1
if ($a[$i] == 1)
$ones++;
// Array element is 2
else
$twos++;
}
$ind = 0;
// If it has at least one 2
// Fill up first 2
if ($twos)
$a[$ind++] = 2;
// Decrease the cnt of
// ones if even
$evenOnes = ($ones % 2 == 0) ? true : false;
if ($evenOnes)
$ones -= 1;
// Fill up with odd count of ones
for ($i = 0; $i < $ones; $i++)
$a[$ind++] = 1;
// Fill up with remaining twos
for ($i = 0; $i < $twos - 1; $i++)
$a[$ind++] = 2;
// If even ones, then fill last position
if ($evenOnes)
$a[$ind++] = 1;
// Print the rearranged array
for ($i = 0; $i < $n; $i++)
echo $a[$i], " ";
}
// Driver code
$a = array( 1, 2, 1, 2, 1 );
$n = count($a);
solve($a, $n);
// This code is contributed by AnkitRai01
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print the re-arranged array
function solve(a, n)
{
let ones = 0, twos = 0;
// Count the number of
// ones and twos in a[]
for (let i = 0; i < n; i++)
{
// If the array element is 1
if (a[i] == 1)
ones++;
// Array element is 2
else
twos++;
}
let ind = 0;
// If it has at least one 2
// Fill up first 2
if (twos > 0)
a[ind++] = 2;
// Decrease the cnt of
// ones if even
let evenOnes = (ones % 2 == 0) ? true : false;
if (evenOnes)
ones -= 1;
// Fill up with odd count of ones
for (let i = 0; i < ones; i++)
a[ind++] = 1;
// Fill up with remaining twos
for (let i = 0; i < twos - 1; i++)
a[ind++] = 2;
// If even ones, then fill last position
if (evenOnes)
a[ind++] = 1;
// Print the rearranged array
for (let i = 0; i < n; i++)
document.write(a[i] + " ");
}
let a = [ 1, 2, 1, 2, 1 ];
let n = a.length;
solve(a, n);
</script>
Producción:
2 1 1 1 2
Complejidad de tiempo: O(n), donde n es el tamaño de la array dada
Espacio auxiliar: O(1), ya que no se utiliza espacio adicional