Cuente los elementos de la array que se pueden maximizar agregando cualquier permutación de los primeros N números naturales

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros, la tarea es determinar el número total de elementos de la array que pueden convertirse en el valor máximo de la array sumando cualquier permutación de [1, N] al valor correspondiente en la array dada.

Ejemplos:

Entrada: N = 3, arr[] = {8, 9, 6}  
Salida: 2
Explicación:
Se pueden agregar las siguientes permutaciones para obtener los valores máximos:
Para que el índice 0 sea el máximo, agregue {3, 1, 2}. Por lo tanto, arr[] = {8 + 3, 9 + 1, 6 + 2} = {11, 10, 8}
Para que el índice 1 sea máximo, agregue {1, 3, 2}. Por lo tanto, arr[] = {8 + 1, 9 + 3, 6 + 2} = {9, 12, 8}
Para que el índice 2 sea máximo, no hay permutación posible tal que arr[2] sea máximo.

Entrada: N = 5 arr[] = {15, 14, 15, 12, 14}
Salida: 4 
Explicación: 
Se pueden agregar las siguientes permutaciones para obtener los valores máximos: 
Para que el índice 0 sea el máximo, agregue {5, 4, 3, 2, 1}. Por lo tanto, arr[] = {15+5, 14+4, 15+3, 12+2, 14+1} = {20, 18, 18, 14, 15} 
Para que el índice 1 sea máximo, agregue {1, 5, 4, 3, 2}. Por lo tanto, arr[] = {15+1, 14+5, 15+4, 12+3, 14+2} = {16, 19, 19, 15, 16} 
Para que el índice 2 sea máximo, agregue {1, 5, 4, 3, 2}. Por lo tanto, arr[] = {15+1, 14+5, 15+4, 12+3, 14+2} = {16, 19, 19, 15, 16} 
Para que el índice 3 sea máximo, no es posible permutación tal que arr[3] se vuelve máximo. 
Para que el índice 4 sea el máximo, agregue {1, 2, 3, 4, 5}. Por lo tanto, arr[] = {15+1, 14+2, 15+3, 12+4, 14+5} = {16, 16, 18, 16, 19}

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de los primeros N números naturales. Ahora, para cada elemento de la array dada, verifique si al agregar alguna de las permutaciones, el elemento actual es el elemento más grande de la array resultante o no. Si se encuentra que es cierto, aumente el conteo y verifique el siguiente elemento.

Complejidad temporal: O(N*N!)
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando el enfoque codicioso para verificar si un elemento de array puede convertirse en máximo al agregar permutaciones o no. Siga los pasos a continuación para resolver el problema anterior:

  1. Ordene la array dada arr[] en orden decreciente.
  2. Inicializa el conteo de variables y marca con 0 .
  3. Recorra la array dada sumando el valor más pequeño, es decir, 1 al número más grande, el segundo valor más pequeño al segundo número más grande, y así sucesivamente.
  4. Además, actualice la marca con el valor máximo encontrado hasta cada índice en el paso anterior.
  5. Antes de actualizar la variable mark , verifique si arr[i] puede volverse máximo cuando se le agrega N , comparándolo con mark . En caso afirmativo, incremente el recuento del contador en 1 .
  6. Después de todos los pasos anteriores, imprima el conteo .

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;
 
// Comparator function to sort the
// given array
bool cmp(int x, int y) { return x > y; }
 
// Function to get the count of values
// that can have the maximum value
void countMaximum(int* a, int n)
{
 
    // Sort array in decreasing order
    sort(a, a + n, cmp);
 
    // Stores the answer
    int count = 0;
 
    // mark stores the maximum value
    // till each index i
    int mark = 0;
 
    for (int i = 0; i < n; ++i) {
 
        // Check if arr[i] can be maximum
        if ((a[i] + n >= mark)) {
            count += 1;
        }
 
        // Update the mark
        mark = max(mark, a[i] + i + 1);
    }
 
    // Print the total count
    cout << count;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 8, 9, 6 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    countMaximum(arr, N);
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to get the count of values
// that can have the maximum value
static void countMaximum(Integer []a, int n)
{
 
    // Sort array in decreasing order
    Arrays.sort(a, Collections.reverseOrder());
 
    // Stores the answer
    int count = 0;
 
    // mark stores the maximum value
    // till each index i
    int mark = 0;
 
    for(int i = 0; i < n; ++i)
    {
         
        // Check if arr[i] can be maximum
        if ((a[i] + n >= mark))
        {
            count += 1;
        }
 
        // Update the mark
        mark = Math.max(mark, a[i] + i + 1);
    }
 
    // Print the total count
    System.out.print(count);
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    Integer arr[] = { 8, 9, 6 };
 
    int N = arr.length;
 
    // Function call
    countMaximum(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function to get the count of values
# that can have the maximum value
def countMaximum(a, n):
     
    # Sort array in decreasing order
    a.sort(reverse = True);
 
    # Stores the answer
    count = 0;
 
    # mark stores the maximum value
    # till each index i
    mark = 0;
 
    for i in range(n):
 
        # Check if arr[i] can be maximum
        if ((a[i] + n >= mark)):
            count += 1;
 
        # Update the mark
        mark = max(mark, a[i] + i + 1);
 
    # Print the total count
    print(count);
 
# Driver Code
if __name__ == '__main__':
     
    # Given array arr
    arr = [ 8, 9, 6 ];
 
    N = len(arr);
 
    # Function call
    countMaximum(arr, N);
 
# This code is contributed by Amit Katiyar

C#

// C# program for the above approach
using System;
using System.Collections;
using System.Linq;
using System.Collections.Generic; 
 
class GFG{
   
// Function to get the count of values
// that can have the maximum value
static void countMaximum(int []a, int n)
{
   
    // Sort array in decreasing order
    a.OrderByDescending(c => c).ToArray();
   
    // Stores the answer
    int count = 0;
   
    // mark stores the maximum value
    // till each index i
    int mark = 0;
   
    for(int i = 0; i < n; ++i)
    {
         
        // Check if arr[i] can be maximum
        if ((a[i] + n >= mark))
        {
            count += 1;
        }
   
        // Update the mark
        mark = Math.Max(mark, a[i] + i + 1);
    }
   
    // Print the total count
    Console.Write(count);
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given array arr[]
    int []arr = { 8, 9, 6 };
   
    int N = arr.Length;
   
    // Function call
    countMaximum(arr, N);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// javascript program for the
// above approach
 
// Function to get the count of values
// that can have the maximum value
function countMaximum(a, n)
{
  
    // Sort array in decreasing order
    a.sort();
    a.reverse();
  
    // Stores the answer
    let count = 0;
  
    // mark stores the maximum value
    // till each index i
    let mark = 0;
  
    for(let i = 0; i < n; ++i)
    {
          
        // Check if arr[i] can be maximum
        if ((a[i] + n >= mark))
        {
            count += 1;
        }
  
        // Update the mark
        mark = Math.max(mark, a[i] + i + 1);
    }
  
    // Print the total count
    document.write(count);
}
  
// Driver Code
 
     // Given array arr[]
    let arr = [ 8, 9, 6 ];
  
    let N = arr.length;
  
    // Function call
    countMaximum(arr, N);
  
 // This code is contributed by avijitmonal1998.
</script>
Producción: 

2

Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por aryan_a y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *