Étant donné un entier pair positif N désignant le nombre de perles distinctes, la tâche consiste à trouver le nombre de façons de faire 2 colliers ayant exactement N/2 perles.
Exemples:
Saisir: N = 2
Sortir: 1
Explication:
La seule façon possible de faire deux colliers est que {1 | 2}.
Saisir: N = 4
Sortir: 3
Explication:
Les façons possibles de faire deux colliers sont {(1, 2) | (3, 4)}, {(1, 3) | (2, 4)}, et {(1, 4) | (2, 3)}.
Approcher: Le problème peut être résolu en utilisant le concept de permutation circulaire et la combinatoire. Suivez les étapes ci-dessous pour résoudre le problème :
- Définissez une fonction, disons factorielle pour calculer la factorielle d’un nombre, en suivant les étapes ci-dessous :
- Cas de base: Si n = 0, puis retour 1.
- Si n != 0, puis appelez récursivement la fonction et retournez n * factoriel(n-1).
- Initialiser une variable, disons, ans comme C(N, N/2), c’est le nombre de façons de choisir N/2 perles de N perles.
- Puisque le collier est circulaire, le nombre de façons de permuter N/2 les perles sont factoriel(N/2 -1), alors multipliez la valeur de ans par factoriel(N/2 -1)*factoriel(N/2-1) puisqu’il y a deux colliers.
- Divisez maintenant le ans par 2. En raison de la distribution symétrique. Par exemple, pour N=2, la distribution {1 | 2} et {2 | 1} sont considérés comme identiques.
- Enfin, après avoir terminé les étapes ci-dessus, imprimez la valeur de ans comme réponse.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; factorielle int(int n) { si (n == 0) retour 1 ; renvoie n * factoriel(n – 1); } long long numOfNecklace(int N) { long long ans = factoriel(N) / (factoriel(N / 2) * factoriel(N / 2)); ans = ans * factoriel(N / 2 – 1); ans = ans * factoriel(N / 2 – 1); ans /= 2; retour ans; } int main() { entier N = 4; cout << numOfNecklace(N) << endl; renvoie 0 ; } |
Java
|
importer java.io.*; classe GFG { int factoriel statique(int n) { si (n == 0) retour 1 ; renvoie n * factoriel(n – 1); } statique long numOfNecklace(int N) { long ans = factoriel(N) / (factoriel(N / 2) * factoriel(N / 2)); ans = ans * factoriel(N / 2 – 1); ans = ans * factoriel(N / 2 – 1); ans /= 2; retour ans; } public static void main(String[] arguments) { entier N = 4; System.out.println(numOfNecklace(N)); } } |
Python3
|
def factoriel(n): si (n == 0) : retour 1 renvoie n * factoriel(n – 1) def numOfNecklace(N): ans = factoriel(N) // (factoriel(N // 2) * factoriel(N // 2)) ans = ans * factoriel(N // 2 – 1) ans = ans * factoriel(N // 2 – 1) et //= 2 retour et if __name__ == ‘__main__’ : N = 4 print(numOfNecklace(N)) |
C#
|
en utilisant le système ; classe GFG{ int factoriel statique(int n) { si (n == 0) retour 1 ; renvoie n * factoriel(n – 1); } statique long numOfNecklace(int N) { long ans = factoriel(N) / (factoriel(N/2) * factoriel(N/2); ans = ans * factoriel(N / 2 – 1); ans = ans * factoriel(N / 2 – 1); ans /= 2; retour ans; } vide public statique Main () { entier N = 4; Console.Write( numOfNecklace(N)); } } |
Javascript
Complexité temporelle : AU)
Espace auxiliaire : O(1)
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.
