Dada una array arr[] que consta de N enteros positivos, la tarea es reorganizar los elementos de la array de modo que el número formado al concatenar el GCD de elementos de la array arr[] del índice 0 al i para cada índice i sea el máximo posible .
Ejemplos:
Entrada: arr[] = {4, 2, 5}
Salida: 5 4 2
Explicación:
X = 511 es el valor máximo de X que se puede obtener entre todos los reordenamientos de arr[].
Las posibles disposiciones de arr[] son:
arr[] = [2, 4, 5] → X = 221
arr[] = [2, 5, 4] → X = 211
arr[] = [4, 2, 5] → X = 421
arr[] = [4, 5, 2] → X = 411
arr[] = [5, 4, 2] → X = 511
arr[] = [5, 2, 4] → X = 511Entrada: arr[] = {2, 4, 6, 8}
Salida: 8 4 6 2
Explicación:
X = 842 es el valor máximo de X que se puede obtener entre todos los reordenamientos de arr[].
Las posibles disposiciones de arr[] son:
arr[] = [4, 6, 8] → X = 422
arr[] = [4, 8, 6] → X = 442
arr[] = [6, 4, 8] → X = 622
arr[] = [6, 8, 4] → X = 622
arr[] = [8, 4, 6] → X = 842
arr[] = [8, 6, 4] → X = 822
Enfoque: el GCD de un número solo es el número en sí mismo, por lo que el primer dígito de X , es decir, X[0] siempre sería igual a arr[0] . Por lo tanto, para garantizar que X sea el máximo entre todos los números obtenibles, arr[0] debe ser máximo. Luego proceda haciendo un seguimiento del GCD del prefijo más largo de arr[] que ya se ha organizado y encuentre los valores de los elementos consecutivos que se colocarán después de este prefijo. Siga los pasos a continuación para resolver el problema anterior:
- El elemento más grande de la array se establece como el primer elemento, por lo que el primer prefijo se organiza correctamente en la array arr[].
- Ahora busque el elemento consecutivo al último elemento del prefijo, es decir, arr[1] .
- Aquí el GCD del prefijo más largo (digamos G ) es igual a arr[0] , por lo tanto, recorra la array restante para encontrar el elemento que da el mayor GCD con G .
- Ahora, intercambie el elemento arr[1] con el elemento que da el GCD máximo con el valor G , actualice el valor de G a este GCD máximo obtenido, es decir, G = GCD(G, arr[1]) .
- Ahora el prefijo fijo más largo se convierte en arr[0] , arr[1] , continúe este proceso para encontrar arr[2] , arr[3] , …, arr[N – 1] , para obtener la array requerida.
- Imprimir reorganizar array después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// obtainable from prefix GCDs
void prefixGCD(int arr[], int N)
{
// Stores the GCD of the
// longest prefix
int gcc;
// Sort the array
sort(arr, arr + N);
// Reverse the array
reverse(arr, arr + N);
// GCD of a[0] is a[0]
gcc = arr[0];
int start = 0;
// Iterate to place the arr[start + 1]
// element at it's correct position
while (start < N - 1) {
int g = 0, s1;
for (int i = start + 1; i < N; i++) {
// Find the element with
// maximum GCD
int gc = __gcd(gcc, arr[i]);
// Update the value of g
if (gc > g) {
g = gc;
s1 = i;
}
}
// Update GCD of prefix
gcc = g;
// Place arr[s1] to it's
// correct position
swap(arr[s1], arr[start + 1]);
// Increment start for the
// remaining elements
start++;
}
// Print the rearranged array
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 1, 2, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
prefixGCD(arr, N);
return 0;
}
Java
//Java program for
// the above approach
import java.util.*;
class GFG{
//Function to find the maximum number
//obtainable from prefix GCDs
static void prefixGCD(int arr[], int N)
{
// Stores the GCD of the
// longest prefix
int gcc;
// Sort the array
Arrays.sort(arr);
// Reverse the array
arr = reverse(arr);
// GCD of a[0] is a[0]
gcc = arr[0];
int start = 0;
// Iterate to place
// the arr[start + 1]
// element at it's
// correct position
while (start < N - 1)
{
int g = 0, s1 = 0;
for (int i = start + 1; i < N; i++)
{
// Find the element with
// maximum GCD
int gc = __gcd(gcc, arr[i]);
// Update the value of g
if (gc > g)
{
g = gc;
s1 = i;
}
}
// Update GCD of prefix
gcc = g;
// Place arr[s1] to it's
// correct position
arr = swap(arr, s1, start + 1);
// Increment start for the
// remaining elements
start++;
}
// Print the rearranged array
for (int i = 0; i < N; i++)
{
System.out.print(arr[i] + " ");
}
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
static int[] reverse(int a[])
{
int i, n = a.length, t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
static int[] swap(int []arr,
int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
//Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = {1, 2, 3, 4};
int N = arr.length;
// Function Call
prefixGCD(arr, N);
}
}
//This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach from math import gcd # Function to find the maximum number # obtainable from prefix GCDs def prefixGCD(arr, N): # Stores the GCD of the # longest prefix gcc = 0 # Sort the array arr = sorted(arr) # Reverse the array arr = arr[::-1] # GCD of a[0] is a[0] gcc = arr[0] start = 0 # Iterate to place the arr[start + 1] # element at it's correct position while (start < N - 1): g = 0 s1 = 0 for i in range(start + 1, N): # Find the element with # maximum GCD gc = gcd(gcc, arr[i]) # Update the value of g if (gc > g): g = gc s1 = i # Update GCD of prefix gcc = g # Place arr[s1] to it's # correct position arr[s1], arr[start + 1] = arr[start + 1], arr[s1] # Increment start for the # remaining elements start += 1 # Print the rearranged array for i in range(N): print(arr[i], end = " ") # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 3, 4 ] N = len(arr) # Function Call prefixGCD(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum number
// obtainable from prefix GCDs
static void prefixGCD(int[] arr, int N)
{
// Stores the GCD of the
// longest prefix
int gcc;
// Sort the array
Array.Sort(arr);
// Reverse the array
arr = reverse(arr);
// GCD of a[0] is a[0]
gcc = arr[0];
int start = 0;
// Iterate to place the
// arr[start + 1] element
// at it's correct position
while (start < N - 1)
{
int g = 0, s1 = 0;
for(int i = start + 1; i < N; i++)
{
// Find the element with
// maximum GCD
int gc = __gcd(gcc, arr[i]);
// Update the value of g
if (gc > g)
{
g = gc;
s1 = i;
}
}
// Update GCD of prefix
gcc = g;
// Place arr[s1] to it's
// correct position
arr = swap(arr, s1, start + 1);
// Increment start for the
// remaining elements
start++;
}
// Print the rearranged array
for(int i = 0; i < N; i++)
{
Console.Write(arr[i] + " ");
}
}
static int __gcd(int a, int b)
{
return b == 0 ? a : __gcd(b, a % b);
}
static int[] reverse(int[] a)
{
int i, n = a.Length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
static int[] swap(int []arr, int i,
int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
//Driver Code
public static void Main()
{
// Given array arr[]
int[] arr = { 1, 2, 3, 4 };
int N = arr.Length;
// Function call
prefixGCD(arr, N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to implement
// the above approach
//Function to find the maximum number
//obtainable from prefix GCDs
function prefixGCD(arr, N)
{
// Stores the GCD of the
// longest prefix
let gcc;
// Sort the array
arr.sort();
// Reverse the array
arr = reverse(arr);
// GCD of a[0] is a[0]
gcc = arr[0];
let start = 0;
// Iterate to place
// the arr[start + 1]
// element at it's
// correct position
while (start < N - 1)
{
let g = 0, s1 = 0;
for (let i = start + 1; i < N; i++)
{
// Find the element with
// maximum GCD
let gc = __gcd(gcc, arr[i]);
// Update the value of g
if (gc > g)
{
g = gc;
s1 = i;
}
}
// Update GCD of prefix
gcc = g;
// Place arr[s1] to it's
// correct position
arr = swap(arr, s1, start + 1);
// Increment start for the
// remaining elements
start++;
}
// Print the rearranged array
for (let i = 0; i < N; i++)
{
document.write(arr[i] + " ");
}
}
function __gcd(a, b)
{
return b == 0 ? a : __gcd(b, a % b);
}
function reverse(a)
{
let i, n = a.length, t;
for (i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
function swap(arr, i, j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver Code
// Given array arr[]
let arr = [1, 2, 3, 4];
let N = arr.length;
// Function Call
prefixGCD(arr, N);
</script>
Producción:
4 2 3 1
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA