Número de formas de elegir un número entero tal que haya exactamente K elementos mayores que él en la array dada

Dada una array arr[] de N elementos y un entero K , la tarea es encontrar el número de formas de elegir un entero X tal que haya exactamente K elementos en la array que sean mayores que X.
Ejemplos: 
 

Entrada: arr[] = {1, 3, 4, 6, 8}, K = 2 
Salida: 2 
X se puede elegir como 4 o 5
Entrada: arr[] = {1, 1, 1}, K = 2 
Salida : 0 
No importa qué número entero elija como X, nunca tendrá exactamente 2 elementos más que él en la array dada. 
 

Enfoque: 
contamos el número total de elementos distintos en la array. Si el recuento de elementos distintos es menor o igual que k, entonces son posibles 0 permutaciones. De lo contrario, la cuenta es igual al número de elementos distintos menos k.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to returns the required count of integers
int countWays(int n, int arr[], int k)
{
 
    if (k <= 0 || k >= n)
        return 0;
 
    unordered_set<int> s(arr, arr+n);
    if (s.size() <= k)
       return 0;
 
    // Return the required count
    return s.size() - k;
}
 
// Driver code
int main()
{
    int arr[] = { 100, 200, 400, 50 };
    int k = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << countWays(n, arr, k);
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
// Function to returns the
// required count of integers
static int countWays(int n, int arr[], int k)
{
 
    if (k <= 0 || k >= n)
        return 0;
    Set<Integer> s = new HashSet<Integer>();
    for(int i = 0; i < n; i++)
        s.add(arr[i]);
         
    if (s.size() <= k)
        return 0;
 
    // Return the required count
    return s.size() - k;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 100, 200, 400, 50 };
    int k = 3;
    int n = arr.length;
    System.out.println(countWays(n, arr, k));
}
}
 
// This code id contributed by
// Surendra_Gangwar

# Python 3 implementation of the approach
 
# Function to returns the required count of integers
def countWays(n, arr, k) :
 
    if (k <= 0 or k >= n) :
        return 0
 
    s = set()
    for element in arr :
        s.add(element)
         
    if (len(s) <= k) :
        return 0;
 
    # Return the required count
    return len(s) - k;
 
 
# Driver code
if __name__ == "__main__" :
     
    arr = [ 100, 200, 400, 50 ]
    k = 3;
    n = len(arr) ;
    print(countWays(n, arr, k))
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to returns the
    // required count of integers
    static int countWays(int n, int []arr, int k)
    {
 
        if (k <= 0 || k >= n)
            return 0;
        HashSet<int> s = new HashSet<int>();
        for(int i = 0; i < n; i++)
            s.Add(arr[i]);
 
        if (s.Count <= k)
            return 0;
 
        // Return the required count
        return s.Count - k;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int []arr = { 100, 200, 400, 50 };
        int k = 3;
        int n = arr.Length;
        Console.WriteLine(countWays(n, arr, k));
    }
}
 
// This code is contributed by Rajput-Ji

<?php
// PHP implementation of the approach
 
// Function to returns the required
// count of integers
function countWays($n, $arr, $k)
{
    if ($k <= 0 || $k >= $n)
        return 0;
 
    $s = array();
    foreach ($arr as $value)
        array_push($s, $value);
    $s = array_unique($s);
         
    if (count($s) <= $k)
        return 0;
 
    // Return the required count
    return count($s) - $k;
}
 
// Driver code
$arr = array(100, 200, 400, 50);
$k = 3;
$n = count($arr);
print(countWays($n, $arr, $k));
 
// This code is contributed by mits
?>

<script>
 
// JavaScript Program to implement
// the above approach
 
// Function to returns the
// required count of integers
function countWays(n, arr, k)
{
 
    if (k <= 0 || k >= n)
        return 0;
    let s = new Set();
    for(let i = 0; i < n; i++)
        s.add(arr[i]);
         
    if (s.size <= k)
        return 0;
 
    // Return the required count
    return s.size - k;
}
 
// Driver Code
 
    let arr = [ 100, 200, 400, 50 ];
    let k = 3;
    let n = arr.length;
    document.write(countWays(n, arr, k));
 
</script>

1

Complejidad de tiempo: O(N * log(N))