Dada una array arr[] que consiste en N enteros, la tarea es encontrar la permutación de los elementos de la array tal que la suma de los elementos de índices impares sea mayor o igual que la suma de los elementos de índices pares.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 1 4 2 3
Explicación:
Considere la permutación de la array dada como {1, 4, 2, 3}.
Ahora, la suma de elementos en índices impares = (4 + 3) = 7 y la suma de elementos en índices pares = (1 + 2) = 3.
Como la suma en elementos de índices impares es mayor que la suma de elementos de índices pares . Por lo tanto, imprima la permutación actual.Entrada: arr[] = {123, 45, 67, 89, 60, 33}
Salida: 33 123 45 89 60 67
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de la array dada e imprimir esa permutación de la array cuya suma de elementos de índices impares es mayor o igual que la suma de elementos de índices pares.
Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar ordenando la array dada y utilizando el enfoque de dos punteros . Siga los pasos a continuación para resolver el problema:
- Ordene la array dada arr[] en orden creciente .
- Inicialice dos variables, digamos i como 0 y j como (N – 1) .
- Iterar sobre el rango [0, N – 1] usando la variable K y realizar los siguientes pasos:
- Si el valor de K es par , imprima el valor de arr[i] e incremente el valor de i en 1 .
- De lo contrario, imprima el valor de arr[j] y disminuya el valor de j en 1 .
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 permutation of
// array elements such that the sum of
// elements at odd āindices is greater
// than sum of elements at even indices
void rearrangeArray(int arr[], int n)
{
// Sort the given array
sort(arr, arr + n);
// Initialize the two pointers
int j = n - 1;
int i = 0;
// Traverse the array arr[]
for (int k = 0; k < n; k++) {
// Check if k is even
if (k % 2 == 0) {
cout << arr[i] << " ";
// Increment the value
// of i
i++;
}
else {
cout << arr[j] << " ";
// Decrement the value
// of j
j--;
}
}
}
// Driver Code
int main()
{
int arr[] = { 123, 45, 67, 89, 60, 33 };
int N = sizeof(arr) / sizeof(arr[0]);
rearrangeArray(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the permutation of
// array elements such that the sum of
// elements at odd āindices is greater
// than sum of elements at even indices
static void rearrangeArray(int arr[], int n)
{
// Sort the given array
Arrays.sort(arr);
// Initialize the two pointers
int j = n - 1;
int i = 0;
// Traverse the array arr[]
for(int k = 0; k < n; k++)
{
// Check if k is even
if (k % 2 == 0)
{
System.out.print(arr[i] + " ");
// Increment the value
// of i
i++;
}
else
{
System.out.print(arr[j] + " ");
// Decrement the value
// of j
j--;
}
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 123, 45, 67, 89, 60, 33 };
int N = arr.length;
rearrangeArray(arr, N);
}
}
// This code is contributed by avijitmondal1998
Python3
# Python3 program for the above approach # Function to find the permutation of # array elements such that the sum of # elements at odd āindices is greater # than sum of elements at even indices def rearrangeArray(arr, n): # Sort the given array arr = sorted(arr) # Initialize the two pointers j = n - 1 i = 0 # Traverse the array arr[] for k in range(n): # Check if k is even if (k % 2 == 0): print(arr[i], end = " ") # Increment the value # of i i += 1 else: print(arr[j], end = " ") # Decrement the value # of j j -= 1 # Driver Code if __name__ == '__main__': arr = [ 123, 45, 67, 89, 60, 33 ] N = len(arr) rearrangeArray(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 permutation of
// array elements such that the sum of
// elements at odd āindices is greater
// than sum of elements at even indices
static void rearrangeArray(int[] arr, int n)
{
// Sort the given array
Array.Sort(arr);
// Initialize the two pointers
int j = n - 1;
int i = 0;
// Traverse the array arr[]
for(int k = 0; k < n; k++)
{
// Check if k is even
if (k % 2 == 0)
{
Console.Write(arr[i] + " ");
// Increment the value
// of i
i++;
}
else
{
Console.Write(arr[j] + " ");
// Decrement the value
// of j
j--;
}
}
}
// Driver Code
public static void Main()
{
int[] arr = { 123, 45, 67, 89, 60, 33 };
int N = arr.Length;
rearrangeArray(arr, N);
}
}
// This code is contributed by subham348
Javascript
<script>
// JavaScript program for the above approach
// Function to find the permutation of
// array elements such that the sum of
// elements at odd āindices is greater
// than sum of elements at even indices
function rearrangeArray(arr, n)
{
// Sort the given array
arr.sort((a, b) => a - b);
// Initialize the two pointers
let j = n - 1;
let i = 0;
// Traverse the array arr[]
for(let k = 0; k < n; k++)
{
// Check if k is even
if (k % 2 == 0)
{
document.write(arr[i] + " ");
// Increment the value
// of i
i++;
}
else
{
document.write(arr[j] + " ");
// Decrement the value
// of j
j--;
}
}
}
// Driver Code
let arr = [ 123, 45, 67, 89, 60, 33 ];
let N = arr.length;
rearrangeArray(arr, N);
// This code is contributed by sanjoy_62.
</script>
33 123 45 89 60 67
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sharathmajjigi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA