Étant donné un tableau arr[] de taille N et un entier K, la tâche consiste à vérifier s’il est possible de diviser le tableau en sous-ensembles strictement croissants de taille au moins K. Si c’est possible, imprimez « Oui« . Sinon, imprimez « Non« .
Exemples:
Saisir: arr[] = {5, 6, 4, 9, 12}, K = 2
Sortir: Oui
Explication:
Une façon possible de diviser le tableau en sous-ensembles d’au moins la taille 2 est, {arr[2](=4), arr[0](=5)} et {arr[1](=6), arr[3](=9), arr[4](=12)}
Saisir: arr[] = {5, 7, 7, 7}, K = 2
Sortir: Non
Approcher: Le problème peut être résolu en utilisant Map pour stocker la fréquence de chaque élément et en divisant le tableau en X sous-ensembles où X est la fréquence de l’élément qui se produit le nombre maximum de fois dans le tableau. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser une carte disons m pour stocker la fréquence des éléments et aussi initialiser une variable mx comme 0 pour stocker la fréquence de l’élément maximum se produisant dans le tableau arr[].
- Parcourir le tableau arr[] en utilisant la variable je, et incrémenter m[arr[i]] par 1 et mettre à jour la valeur de mx à max(mx, m[arr[i]]).
- Maintenant si N/mx>= K puis imprime « Oui” car il s’agit du nombre maximum d’éléments qu’un sous-ensemble peut avoir.
- Sinon, imprimez « Non« .
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; chaîne ifPossible(int arr[], entier N, entier K) { map entier mx = 0; pour (int i = 0; i < N; i++) { m[arr[i]]+= 1; mx = max(mx, m[arr[i]]); } int sz = N / mx; si (sz >= K) { retourner « Oui » ; } autre { retourner « Non » ; } } int main() { int arr[] = { 5, 6, 4, 9, 12 } ; entier K = 2; int N = taillede(arr) / taillede(arr[0]); cout << siPossible (arr, N, K); renvoie 0 ; } |
Java
|
importer java.util.HashMap; classe publique GFG { Chaîne statique ifPossible(int arr[], entier N, entier K) { HashMap = new HashMap entier mx = 0; pour (int i = 0; i < N; i++) { m.put(arr[i], m.getOrDefault(arr[i], 0) + 1); mx = Math.max(mx, m.get(arr[i])); } int sz = N / mx; si (sz >= K) { retourner « Oui » ; } autre { retourner « Non » ; } } public static void main(String[] arguments) { int arr[] = { 5, 6, 4, 9, 12 } ; entier K = 2; int N = longueur arr; System.out.println(ifPossible(arr, N, K)); } } |
Python3
|
def ifPossible(arr, N, K): m = {} mx = 0 pour i dans la plage (N): si arr[i] dans M: m[arr[i]]+= 1 autre: m[arr[i]]= 1 mx = max(mx, m[arr[i]]) sz = N // mx si (sz >= K) : retourner « Oui » autre: retourner « Non » if __name__ == ‘__main__’ : arr = [ 5, 6, 4, 9, 12 ] K = 2 N = len(arr) print(siPossible(arr, N, K)) |
C#
|
en utilisant le système ; en utilisant System.Collections.Generic ; classe GFG { chaîne statique ifPossible(int []arr, int N, int K) { Dictionnaire entier mx = 0; pour (int i = 0; i < N; i++) { if(m.ContainsKey(arr[i])) m[arr[i]]+= 1; autre m.Ajouter(arr[i],1); mx = Math.Max(mx, m[arr[i]]); } int sz = N / mx; si (sz >= K) { retourner « Oui » ; } autre { retourner « Non » ; } } public statique vide Main() { entier []arr = { 5, 6, 4, 9, 12 } ; entier K = 2; int N = arr.Longueur; Console.Write(ifPossible(arr, N, K)); } } |
Javascript
Complexité temporelle : O(N*log(N))
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
