Optimisation d'une boucle while en Java

Question

J'ai travaillé sur la liste des problèmes d'algorithme de HackerRank. Je continue d'avoir une erreur de timeout sur cette boucle et je me demandais s'il y avait un moyen de l'accélérer? Certains googling préliminaire ne s'est pas montré beaucoup.

Editer pour contexte: Le problème a deux kangourous, chacun d'eux a une position de départ (k1, k2) et une vitesse de déplacement (v1, v2). Je dois déterminer s'ils atterriront au même endroit au même moment.

static String kangaroo(int k1, int v1, int k2, int v2) { 
    int diff = Math.abs(k1 - k2); 
    int newDiff = 0; 
    String output = ""; 

    while (true){ 
     k1 += v1; 
     k2 += v2; 
     newDiff = Math.abs(k1 - k2);  
     if (k1 == k2){ 
      output = "YES"; 
      break; 
     } 
     else if (newDiff > diff){ 
      output = "NO"; 
      break; 
     } 
    } 
    return output; 
} 

Answer 1

Votre code est assez rapide (O(n)), mais ce problème peut être résolu en temps constant (O(1)), car elle ne repose que sur l'état de l'intersection de deux lignes étant un nombre entier.

static String kangaroo(int k1, int v1, int k2, int v2) { 
    float x = (k2 - k1)/(v1 - v2); 
    if(x == (int) x) { //check if the intersection point is an integer 
     return "YES"; 
    } 
    return "NO"; 
}