Dada una array arr[] que consta de una permutación de los primeros N números naturales, la tarea es encontrar el valor máximo posible de ΣGCD(arr[i], i) ( indexación basada en 1 ) reorganizando los elementos de la array dados.
Ejemplos:
Entrada: arr[] = { 2, 1}
Salida: 6
Explicación:
Reorganizar la array dada a { 2, 1}.
ΣGCD(array[i], i) = MCD(array[1], 1) + MCD(array[2], 2) = MCD(2, 1) + MCD(1, 2)= 2 Reorganizando la array dada
a { 1, 2 }.
ΣGCD(arr[i], i) = GCD(arr[1], 1) + GCD(arr[2], 2) = GCD(1, 1) + GCD(2, 2) = 3 Por lo tanto, la salida
requerida es 3Entrada: arr[] = { 4, 5, 3, 2, 1 }
Salida: 15
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y generar todas las permutaciones posibles de la array dada y, para cada permutación, encontrar el valor de ΣGCD(arr[i], i) . Finalmente, imprima el valor máximo de ΣGCD(arr[i], i) de cada permutación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
int findMaxValByRearrArr(int arr[], int N)
{
// Sort the array in
// ascending order
sort(arr, arr + N);
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Generate all possible
// permutations of the array
do {
// Stores sum of GCD(arr[i], i)
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += __gcd(i + 1, arr[i]);
}
// Update res
res = max(res, sum);
} while (next_permutation(arr, arr + N));
return res;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMaxValByRearrArr(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
static int findMaxValByRearrArr(int arr[], int N)
{
// Sort the array in
// ascending order
Arrays.sort(arr);
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Generate all possible
// permutations of the array
do {
// Stores sum of GCD(arr[i], i)
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update sum
sum += __gcd(i + 1, arr[i]);
}
// Update res
res = Math.max(res, sum);
} while (next_permutation(arr));
return res;
}
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
static boolean next_permutation(int[] p)
{
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1 };
int N = arr.length;
System.out.print(findMaxValByRearrArr(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Function to find the maximum sum of # GCD(arr[i], i) by rearranging the array def findMaxValByRearrArr(arr, N): # Sort the array in # ascending order arr.sort() # Stores maximum sum of GCD(arr[i], i) # by rearranging the array elements res = 0 # Generate all possible # permutations of the array while (True): # Stores sum of GCD(arr[i], i) Sum = 0 # Traverse the array for i in range(N): # Update sum Sum += __gcd(i + 1, arr[i]) # Update res res = max(res, Sum) if (not next_permutation(arr)): break return res def __gcd(a, b): if b == 0: return a else: return __gcd(b, a % b) def next_permutation(p): for a in range(len(p) - 2, -1, -1): if (p[a] < p[a + 1]): b = len(p) - 1 while True: if (p[b] > p[a]): t = p[a] p[a] = p[b] p[b] = t a += 1 b = len(p) - 1 while a < b: t = p[a] p[a] = p[b] p[b] = t a += 1 b -= 1 return True b -= 1 return False # Driver code arr = [ 3, 2, 1 ] N = len(arr) print(findMaxValByRearrArr(arr, N)) # This code is contributed by divyesh072019
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
static int findMaxValByRearrArr(int []arr, int N)
{
// Sort the array in
// ascending order
Array.Sort(arr);
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Generate all possible
// permutations of the array
do
{
// Stores sum of GCD(arr[i], i)
int sum = 0;
// Traverse the array
for (int i = 0; i < N; i++)
{
// Update sum
sum += __gcd(i + 1, arr[i]);
}
// Update res
res = Math.Max(res, sum);
} while (next_permutation(arr));
return res;
}
static int __gcd(int a, int b)
{
return b == 0? a:__gcd(b, a % b);
}
static bool next_permutation(int[] p)
{
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1; a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1 };
int N = arr.Length;
Console.Write(findMaxValByRearrArr(arr, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
function findMaxValByRearrArr(arr, N)
{
// Sort the array in
// ascending order
arr.sort();
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
let res = 0;
// Generate all possible
// permutations of the array
do {
// Stores sum of GCD(arr[i], i)
let sum = 0;
// Traverse the array
for (let i = 0; i < N; i++) {
// Update sum
sum += __gcd(i + 1, arr[i]);
}
// Update res
res = Math.max(res, sum);
} while (next_permutation(arr));
return res;
}
function __gcd(a, b)
{
return b == 0? a:__gcd(b, a % b);
}
function next_permutation(p)
{
for (let a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (let b = p.length - 1;; --b)
if (p[b] > p[a])
{
let t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
let arr = [ 3, 2, 1 ];
let N = arr.length;
document.write(findMaxValByRearrArr(arr, N));
// This code is contributed by souravghosh0416.
</script>
Producción:
6
Complejidad temporal: O(N!)
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Valor máximo posible de GCD(X, Y) = min(X, Y)
Por lo tanto, el valor máximo posible de GCD(i, arr[i]) = min(i, arr[i])
Si la array está ordenada entonces i = arr[i] y el valor de MCD(i, arr[i]) = i
ΣGCD(arr[i], i) = Σi = N * (N + 1) / 2
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res , para almacenar la suma máxima posible de ΣGCD(arr[i], i) .
- Actualizar res = (N * (N + 1) / 2) .
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
int findMaxValByRearrArr(int arr[], int N)
{
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Update res
res = (N * (N + 1)) / 2;
return res;
}
// Driver Code
int main()
{
int arr[] = { 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMaxValByRearrArr(arr, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
static int findMaxValByRearrArr(int arr[], int N)
{
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Update res
res = (N * (N + 1)) / 2;
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 2, 1 };
int N = arr.length;
System.out.print(findMaxValByRearrArr(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to implement # the above approach # Function to find the maximum sum of # GCD(arr[i], i) by rearranging the array def findMaxValByRearrArr(arr, N): # Stores maximum sum of GCD(arr[i], i) # by rearranging the array elements res = 0; # Update res res = (N * (N + 1)) // 2; return res; # Driver Code if __name__ == '__main__': arr = [ 3, 2, 1 ]; N = len(arr); print(findMaxValByRearrArr(arr, N)); # This code contributed by shikhasingrajput
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
static int findMaxValByRearrArr(int []arr, int N)
{
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
int res = 0;
// Update res
res = (N * (N + 1)) / 2;
return res;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 2, 1 };
int N = arr.Length;
Console.Write(findMaxValByRearrArr(arr, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Function to find the maximum sum of
// GCD(arr[i], i) by rearranging the array
function findMaxValByRearrArr(arr, N)
{
// Stores maximum sum of GCD(arr[i], i)
// by rearranging the array elements
let res = 0;
// Update res
res = parseInt((N * (N + 1)) / 2, 10);
return res;
}
let arr = [ 3, 2, 1 ];
let N = arr.length;
document.write(findMaxValByRearrArr(arr, N));
</script>
Producción:
6
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por daljeetsingh22sk9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA