![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.png)
Étant donné deux entiers positifs N et K, la tâche consiste à imprimer le nombre minimum de nombres nécessaires pour obtenir la somme égale à K, en ajoutant une seule fois tout élément des N premiers nombres naturels. S’il est impossible d’obtenir la somme égale à K, puis imprimez « -1« .
Exemples:
Saisir: N = 5, K = 10
Sortir: 3
Explication:
Le moyen le plus optimal est de choisir le nombre {1, 4, 5} auquel se résumera jusqu’à 10.
Par conséquent, imprimez 3 qui est le nombre minimum d’éléments nécessaires.
Saisir: N = 5, K = 1000
Sortir: -1
Explication:
Il est impossible d’obtenir la somme égale à 1000.
Approcher: Le problème peut être résolu en utilisant l’algorithme glouton. Suivez les étapes ci-dessous pour résoudre ce problème :
- Si K est supérieur à la somme des N premiers nombres naturels, puis l’impression « -1 » puis revenir.
- Si K est inférieur à égal à N, puis imprimer 1 puis revenir.
- Sinon, initialisez la variable disons somme, et compter comme 0 pour stocker la somme et le nombre minimum de nombres nécessaires.
- Itérer jusqu’à N est supérieur à égal à 1 et somme est inférieur à K et effectuez les étapes suivantes:
- Incrémenter compter par 1, somme par N, puis décrémenter le N par 1.
- Enfin, si aucun des cas ci-dessus ne satisfait, imprimez le compter 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 ; int Minimum(int N, int K) { somme entière = N * (N + 1) / 2 ; si (K > somme) retour -1 ; si (K <= N) retour 1 ; somme = 0; nombre entier = 0 ; tandis que (N >= 1 && somme < K) { compte += 1 ; somme += N; N-= 1 ; } nombre de retours ; } int main() { entier N = 5, K = 10; cout << (Minimum (N, K)); renvoie 0 ; } |
Java
|
importer java.io.*; classe GFG { statique int Minimum(int N, int K) { somme entière = N * (N + 1) / 2 ; si (K > somme) retour -1 ; si (K <= N) retour 1 ; somme = 0; nombre entier = 0 ; tandis que (N >= 1 && somme < K) { compte += 1 ; somme += N; N-= 1 ; } nombre de retours ; } public static void main(String[] arguments) { entier N = 5, K = 10; System.out.println(Minimum(N, K)); } } |
Python3
|
par défaut Minimum(N, K) : somme = N * (N + 1) // 2 si (K > somme) : retour -1 si (K <= N) : retour 1 somme = 0 compte = 0 tandis que (N >= 1 et somme < K) : compte += 1 somme += N N -= 1 nombre de retours if __name__ == ‘__main__’ : N = 5 K = 10 imprimer (Minimum (N, K)) |
C#
|
en utilisant le système ; classe GFG{ statique int Minimum(int N, int K) { somme entière = N * (N + 1) / 2 ; si (K > somme) retour -1 ; si (K <= N) retour 1 ; somme = 0; nombre entier = 0 ; tandis que (N >= 1 && somme < K) { compte += 1 ; somme += N; N-= 1 ; } nombre de retours ; } vide public statique Main() { entier N = 5, K = 10; Console.Write(Minimum(N, K)); } } |
Javascript
Complexité temporelle : AU)
Espace auxiliaire : O(1)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts mathématiques importants pour la programmation compétitive avec le Mathématiques essentielles pour le cours CP à un prix adapté aux étudiants. 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.
![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)
