Compruebe si N elementos se pueden dividir en K grupos de tamaño único

Dados los números enteros N y K , la tarea es verificar si es posible dividir N números en K grupos de modo que todos los K grupos sean de diferente tamaño y cada parte tenga al menos un número.

Ejemplos:

Entrada: N = 5, K = 2
Salida:
Explicación: 5 números se pueden dividir en 2 partes de diferente tamaño. El tamaño posible de los grupos puede ser (1, 4) y (2, 3).

Entrada: N = 3, K = 3
Salida: No
Explicación: 3 números no se pueden dividir en 3 grupos de tamaño único.

 

Enfoque: El problema se puede resolver sobre la base de la siguiente observación. 

Para dividir N números en K grupos de modo que cada grupo tenga al menos un número y no haya dos grupos del mismo tamaño:

  • Debe haber al menos K números. Si N < K, entonces la división no es posible.
  • Si N > K, entonces los grupos K serán al menos de tamaño 1, 2, 3, 4. . . k Entonces N debe ser al menos K*(K + 1)/2. 
    Por tanto, la condición a cumplir es N ≥ K*(K + 1)/2.

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

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to break N in K groups
void checkPartition(int N, int K)
{
    // Invalid case
    if (N < (K * (K + 1)) / 2) {
        cout << "No";
    }
    else {
        cout << "Yes";
    }
}
 
// Driver code
int main()
{
    int N = 6, K = 5;
 
    checkPartition(N, K);
    return 0;
}

C

// C code to implement above approach
#include <stdio.h>
 
// Function to check if it is possible
// to break N in K groups
void checkPartition(int N, int K)
{
    // Invalid case
    if (N < (K * (K + 1)) / 2) {
        printf("No");
    }
    else {
        printf("Yes");
    }
}
 
// Driver code
int main()
{
    int N = 6, K = 5;
 
    checkPartition(N, K);
    return 0;
}

Java

// Java code to implement above approach
import java.io.*;
 
class GFG {
 
    // Function to check if it is possible
    // to break N in K groups
    public static void checkPartition(int N, int K)
    {
        // Invalid case
        if (N < (K * (K + 1) / 2)) {
            System.out.print("No");
        }
        else {
            System.out.print("Yes");
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 6, K = 5;
        checkPartition(N, K);
    }
}

Python3

# Python code to implement above approach
 
def checkPartition(N, K):
 
    # Invalid case
    if (N < (K*(K + 1))//2):
        print("No")
    else:
        print("Yes")
 
# Driver code
if __name__ == '__main__':
    N = 6
    K = 5
    checkPartition(N, K)

C#

// C# code to implement above approach
using System;
class GFG {
 
  // Function to check if it is possible
  // to break N in K groups
  public static void checkPartition(int N, int K)
  {
 
    // Invalid case
    if (N < (K * (K + 1) / 2)) {
      Console.Write("No");
    }
    else {
      Console.Write("Yes");
    }
  }
 
  // Driver code
  public static void Main()
  {
    int N = 6, K = 5;
    checkPartition(N, K);
  }
}
 
// This code is contributed by saurabh_jaiswal.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to check if it is possible
       // to break N in K groups
       function checkPartition(N, K)
       {
        
           // Invalid case
           if (N < Math.floor((K * (K + 1)) / 2)) {
               document.write("No");
           }
           else {
               document.write("Yes");
           }
       }
 
       // Driver code
 
       let N = 6, K = 5;
 
       checkPartition(N, K);
 
 // This code is contributed by Potta Lokesh
   </script>
Producción

No

Complejidad Temporal: O(1)
Espacio Auxiliar: O(1).

Publicación traducida automáticamente

Artículo escrito por priyanshusingh241202 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 *