Maximizando los elementos con a[i+1] > a[i]

Dada una array de N enteros, reorganice los elementos de la array de modo que el siguiente elemento de la array sea mayor que el elemento anterior ( >  ). 
Ejemplos:
 

Entrada: arr[] = {20, 30, 10, 50, 40} 
Salida: 4 
Reorganizamos la array como 10, 20, 30, 40, 50. Como 20 > 10, 30 > 20, 40 > 30, 50 > 40, por lo que obtenemos 4 índices i tales que  >  . 
Entrada: arr[] = {200, 100, 100, 200} 
Salida: 2 
Obtenemos un arreglo óptimo como 100 200 100 200.

Si todos los elementos son distintos, entonces la respuesta es simplemente n-1 donde n es el número de elementos en la array. Si hay elementos que se repiten, la respuesta es n – max_freq.
 

#include<bits/stdc++.h>
using namespace std;
 
// returns the number of positions where A(i + 1) is
// greater than A(i) after rearrangement of the array
int countMaxPos(int arr[], int n)
{
 
    // Creating a HashMap containing char
    // as a key and occurrences as a value
    unordered_map<int, int> map;
     
    for (int i = 0; i < n; i++ ) {
        if (map.count(arr[i]))
            map.insert({arr[i], (map.count(arr[i]) + 1)});
        else
            map.insert({arr[i], 1});
    }
     
    // Find the maximum frequency
    int max_freq = 0;
 
    for (auto i : map) {
        if (max_freq < i.second)
        {
            max_freq = i.second;
        }
    }
    return n - max_freq;
}
 
// Driver code
int main()
{
    int arr[] = { 20, 30, 10, 50, 40 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << (countMaxPos(arr, n));
}
 
// This code is contributed by Rajput-Ji

import java.util.*;
 
class GFG {
 
    // returns the number of positions where A(i + 1) is
    // greater than A(i) after rearrangement of the array
    static int countMaxPos(int[] arr)
    {
        int n = arr.length;
 
        // Creating a HashMap containing char
        // as a key and occurrences as  a value
        HashMap<Integer, Integer> map
            = new HashMap<Integer, Integer>();
        for (int x : arr) {
            if (map.containsKey(x))
                map.put(x, map.get(x) + 1);
            else
                map.put(x, 1);
        }
 
        // Find the maximum frequency
        int max_freq = 0;
        for (Map.Entry entry : map.entrySet())
            max_freq = Math.max(max_freq, (int)entry.getValue());
 
        return n - max_freq;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 20, 30, 10, 50, 40 };
        System.out.println(countMaxPos(arr));
    }
}

# Python3 implementation of the above approach
 
# Returns the number of positions where
# A(i + 1) is greater than A(i) after
# rearrangement of the array
def countMaxPos(arr):
     
    n = len(arr)
 
    # Creating a HashMap containing char
    # as a key and occurrences as a value
    Map = {}
    for x in arr:
        if x in Map:
            Map[x] += 1
        else:
            Map[x] = 1
         
    # Find the maximum frequency
    max_freq = 0
    for entry in Map:
        max_freq = max(max_freq, Map[entry])
 
    return n - max_freq
 
# Driver code
if __name__ == "__main__":
     
    arr = [20, 30, 10, 50, 40]
    print(countMaxPos(arr))
     
# This code is contributed by Rituraj Jain

// C# implementation of the approach
using System;
using System.Collections.Generic;            
 
class GFG
{
 
    // returns the number of positions where
    // A(i + 1) is greater than A(i) after
    // rearrangement of the array
    static int countMaxPos(int[] arr)
    {
        int n = arr.Length;
 
        // Creating a HashMap containing char
        // as a key and occurrences as a value
        Dictionary<int,
                   int> map = new Dictionary<int,
                                             int>();
        foreach (int x in arr)
        {
            if (map.ContainsKey(x))
                map[x] = map[x] + 1;
            else
                map.Add(x, 1);
        }
 
        // Find the maximum frequency
        int max_freq = 0;
        foreach(KeyValuePair<int, int> entry in map)
            max_freq = Math.Max(max_freq, entry.Value);
 
        return n - max_freq;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] arr = { 20, 30, 10, 50, 40 };
        Console.WriteLine(countMaxPos(arr));
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript implementation of the approach
 
// returns the number of positions where
// A(i + 1) is greater than A(i) after
// rearrangement of the array
function countMaxPos(arr) {
    let n = arr.length;
 
    // Creating a HashMap containing char
    // as a key and occurrences as a value
    let map = new Map();
 
    for (let x of arr) {
        if (map.has(x))
            map.set(x, map.get(x) + 1);
        else
            map.set(x, 1);
    }
 
    // Find the maximum frequency
    let max_freq = 0;
 
    for (let entry of map)
        max_freq = Math.max(max_freq, entry[1]);
 
    console.log(max_freq, n)
    return n - max_freq;
}
 
// Driver code
 
let arr = [20, 30, 10, 50, 40];
document.write(countMaxPos(arr));
 
 
 
// This code is contributed by _saurabh_jaiswal
</script>

4

Complejidad temporal: O(n)
Espacio auxiliar: O(n)