Verifique si la array dada se puede reducir a ceros con la operación dada realizada un número dado de veces

Dada una array arr[] de N enteros y un entero K , la tarea es encontrar si los elementos de la array dados se pueden hacer 0 si la operación dada se aplica exactamente K veces. En una sola operación, el elemento más pequeño de la array se restará de todos los elementos distintos de cero de la array.
Ejemplos: 
 

Entrada: arr[] = {1, 1, 2, 3}, K = 3 
Salida: Sí 
K = 1 -> arr[] = {0, 0, 1, 2} 
K = 2 -> arr[] = { 0, 0, 0, 1} 
K = 3 -> arr[] = {0, 0, 0, 0}
Entrada: arr[] = {11, 2, 3, 4}, K = 3 
Salida: No 
La array requiere 4 operaciones. 
 

Acercarse: 
 

• La observación principal aquí es que el número mínimo no importa en cada operación, supongamos que X es el número mínimo, entonces todas las ocurrencias de X serán 0 en la operación actual y otros elementos se reducirán en X .
• Podemos concluir que todos los elementos idénticos serán 0 en la misma operación.
• Entonces, digamos que en las operaciones Q , la array completa se convierte en 0 , es igual a la cantidad de elementos únicos en la array.
• Si Q = K , entonces la respuesta es Sí , de lo contrario , imprima No.
• El número de elementos únicos se puede obtener usando set .

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if the array
// can be reduced to 0s with the given
// operation performed given number of times
bool check(int arr[], int N, int K)
{
    // Set to store unique elements
    set<int> unique;
 
    // Add every element of the array
    // to the set
    for (int i = 0; i < N; i++)
        unique.insert(arr[i]);
 
    // Count of all the unique elements
    // in the array
    if (unique.size() == K)
        return true;
    return false;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 1, 2, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    if (check(arr, N, K))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
// Function that returns true if the array
// can be reduced to 0s with the given
// operation performed given number of times
static boolean check(int arr[], int N, int K)
{
    // Set to store unique elements
    HashSet<Integer> unique = new HashSet<Integer>();
 
 
    // Add every element of the array
    // to the set
    for (int i = 0; i < N; i++)
        unique.add(arr[i]);
 
    // Count of all the unique elements
    // in the array
    if (unique.size() == K)
        return true;
    return false;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 1, 2, 3 };
    int N = arr.length;
    int K = 3;
    if (check(arr, N, K))
        System.out.println("Yes");
    else
        System.out.println("No");
}
}
 
// This code has been contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Function that returns true if the array
# can be reduced to 0s with the given
# operation performed given number of times
def check(arr, N, K):
     
    # Set to store unique elements
    unique = dict()
 
    # Add every element of the array
    # to the set
    for i in range(N):
        unique[arr[i]] = 1
 
    # Count of all the unique elements
    # in the array
    if len(unique) == K:
        return True
    return False
 
# Driver code
arr = [1, 1, 2, 3]
N = len(arr)
K = 3
if (check(arr, N, K) == True):
    print("Yes")
else:
    print("No")
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function that returns true if the array
// can be reduced to 0s with the given
// operation performed given number of times
public static bool check(int[] arr, int N, int K)
{
    // Set to store unique elements
    HashSet<int> unique = new HashSet<int>();
 
 
    // Add every element of the array
    // to the set
    for (int i = 0; i < N; i++)
    {
        unique.Add(arr[i]);
    }
 
    // Count of all the unique elements
    // in the array
    if (unique.Count == K)
    {
        return true;
    }
    return false;
}
 
// Driver code
public static void Main(string[] args)
{
    int[] arr = new int[] {1, 1, 2, 3};
    int N = arr.Length;
    int K = 3;
    if (check(arr, N, K))
    {
        Console.WriteLine("Yes");
    }
    else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by shrikanth13

<?php
// PHP implementation of the approach
 
// Function that returns true if the array
// can be reduced to 0s with the given
// operation performed given number of times
function check( &$arr, $N, $K)
{
     
    // Add in Set only unique elements
    $unique = array_unique($arr);
 
    // Count of all the unique elements
    // in the array
    if (count($unique) == $K)
        return true;
    return false;
}
 
// Driver code
$arr = array( 1, 1, 2, 3 );
$N = count($arr);
$K = 3;
if (check($arr, $N, $K))
    echo "Yes";
else
    echo "No";
     
// This code has been contributed
// by Rajput-Ji
?>

<script>
 
// Javascript implementation of the approach
 
// Function that returns true if the array
// can be reduced to 0s with the given
// operation performed given number of times
function check(arr, N, K)
{
    // Set to store unique elements
    var unique = new Set();
 
    // Add every element of the array
    // to the set
    for (var i = 0; i < N; i++)
        unique.add(arr[i]);
 
    // Count of all the unique elements
    // in the array
    if (unique.size == K)
        return true;
    return false;
}
 
// Driver code
var arr = [1, 1, 2, 3];
var N = arr.length;
var K = 3;
if (check(arr, N, K))
    document.write( "Yes");
else
    document.write( "No");
 
</script>

Yes

Complejidad de tiempo: O (nlogn), donde n es el tamaño de la array dada.
Espacio auxiliar: O(n), donde se utiliza un espacio extra de tamaño n para crear un conjunto.