Trouvez l'élève qui remplacera la craie

1894. Trouvez l'élève qui remplacera la craie

Difficulté :Moyen

Sujets : Tableau, recherche binaire, simulation, somme de préfixes

Il y a n élèves dans une classe numérotés de 0 à n - 1. Le professeur donnera à chaque élève un problème en commençant par l'élève numéro 0, puis l'élève numéro 1, et ainsi de suite jusqu'à ce que l'enseignant atteigne le numéro d'élève n. - 1. Après cela, l'enseignant redémarrera le processus en commençant à nouveau par l'élève numéro 0.

Vous recevez une craie de tableau d'entiers indexés à 0 et un k entier. Il y a initialement k morceaux de craie. Lorsque l'élève numéro i se voit confier un problème à résoudre, il utilisera des morceaux de craie [i] pour résoudre ce problème. Cependant, si le nombre actuel de morceaux de craie est strictement inférieur à la craie[i], alors il sera demandé au numéro d'élève i de remplacer la craie.

Renvoyer l'index de l'élève qui remplacera les morceaux de craie.

Exemple 1 :

• Entrée : craie = [5,1,5], k = 22
• Sortie : 0
• Explication : Les élèves se déplacent à tour de rôle comme suit :
  • L'élève numéro 0 utilise 5 craies, donc k = 17.
  • L'élève numéro 1 utilise 1 craie, donc k = 16.
  • L'élève numéro 2 utilise 5 craies, donc k = 11.
  • L'élève numéro 0 utilise 5 craies, donc k = 6.
  • L'élève numéro 1 utilise 1 craie, donc k = 5.
  • L'élève numéro 2 utilise 5 craies, donc k = 0.
  • L'élève numéro 0 n'a pas assez de craie, il devra donc la remplacer.

Exemple 2 :

• Entrée : craie = [3,4,1,2], k = 25
• Sortie : 1
• Explication : Les élèves se déplacent à tour de rôle comme suit :
  • L'élève numéro 0 utilise 3 craies donc k = 22.
  • L'élève numéro 1 utilise 4 craies donc k = 18.
  • L'élève numéro 2 utilise 1 craie donc k = 17.
  • L'élève numéro 3 utilise 2 craies donc k = 15.
  • L'élève numéro 0 utilise 3 craies donc k = 12.
  • L'élève numéro 1 utilise 4 craies donc k = 8.
  • L'élève numéro 2 utilise 1 craie donc k = 7.
  • L'élève numéro 3 utilise 2 craies donc k = 5.
  • L'élève numéro 0 utilise 3 craies donc k = 2.
  • L'élève numéro 1 n'a pas assez de craie, il devra donc la remplacer.

Contraintes :

• chalk.length == n
• 1 <= n <= 10₅
• 1 <= craie[i] <= 10₅
• 1 <= k <= 10₉

Indice :

1. Soustrayez la somme de la craie de k jusqu'à ce que k soit inférieur à la somme de la craie.
2. Parcourez maintenant le tableau. Si chalk[i] est inférieur à k, voici la réponse. Sinon, soustrayez la craie[i] de k et continuez.

Solution :

Décomposons le problème étape par étape :

Approche:

1. Consommation totale de craie :
   Tout d’abord, calculez la quantité totale de craie nécessaire pour un tour complet (de l’élève 0 à l’élève n-1). Cela nous aidera à réduire la valeur de k en tenant compte du nombre de tours complets qui peuvent être couverts par k morceaux de craie.

2. Réduire k par Modulo :
   Si k est plus grand que le total de craie requis pour un tour complet, nous pouvons simplifier le problème en prenant k % total_chalk. Cette opération nous donnera la craie restante après autant de tours complets que possible, nous laissant avec un plus petit problème à résoudre.

3. Trouvez l'élève qui manque de craie :
   Parcourez la consommation de craie de chaque élève, en la soustrayant de k jusqu'à ce que k devienne inférieur aux besoins en craie de l'élève actuel. L'index de cet élève est notre réponse.

Exemple de procédure pas à pas :

Prenons un exemple craie = [3, 4, 1, 2] et k = 25 :

1. Consommation totale de craie :

   text{total_chalk} = 3 + 4 + 1 + 2 = 10

1. Réduire k :

   k % 10 = 25 % 10 = 5

Maintenant, nous avons k = 5 après avoir soustrait autant de tours complets que possible.

1. Trouver l'étudiant :
   • L'élève 0 utilise 3 craies, donc k = 5 - 3 = 2.
   • L'élève 1 a besoin de 4 craies, mais k = 2, ce qui est inférieur à 4.
   • Par conséquent, l'élève 1 sera celui qui devra remplacer la craie.

Implémentons cette solution en PHP : 1894. Trouvez l'élève qui remplacera la craie

  
  
  Explanation:




Total Chalk Sum: We sum up all the chalk requirements to get the total for one complete round.

Modulo Operation: Using modulo with k, we get the effective number of chalks to distribute after full rounds.

Find the Student: We then iterate through the students, checking if the remaining chalk is sufficient. The first time it's insufficient, that student's index is the answer.



  
  
  Complexity:




Time Complexity: O(n) — we sum the array and then iterate through it once.

Space Complexity: O(1) — only a few variables are used, independent of the input size.


This approach ensures that the problem is solved efficiently even for large inputs.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
  

            
        
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!