Estoy viendo el problema de HackerRank Saltos de línea numérica :
Estás coreografiando un espectáculo de circo con varios animales. Para un acto, se le dan dos canguros en una recta numérica listos para saltar en la dirección positiva (es decir, hacia el infinito positivo).
- El primer canguro comienza en la ubicación 𝑥1 y se mueve a una velocidad de 𝑣1 metros por salto.
- El segundo canguro comienza en la ubicación 𝑥2 y se mueve a una velocidad de 𝑣2 metros por salto.
Tienes que encontrar una manera de llevar a ambos canguros al mismo lugar al mismo tiempo como parte del espectáculo. Si es posible, devuelva SÍ, de lo contrario, devuelva NO.
Ejemplo
𝑥1 = 2
𝑣1 = 1
𝑥2 = 1
𝑣2 = 2Después de un salto, ambos están en 𝑥 = 3, (𝑥1 + 𝑣1 = 2 + 1, 𝑥2 + 𝑣2 = 1 + 2), por lo que la respuesta es SÍ.
Restricciones
0 ≤ 𝑥1 < 𝑥2 ≤ 10000
1 ≤ 𝑣1 ≤ 10000
1 ≤ 𝑣2 ≤ 10000
El algoritmo que escribí no pasa todas las pruebas en HackerRank, ¿no puedo ver dónde me estoy equivocando?
function kangaroo(x1, v1, x2, v2) { let firstKangaroo = x1 + v1; let secondKangaroo= x2 + v2; let trueFalse = false; let maxLimit = 10000; let i = 0; for(;i <= maxLimit;i++) { if(firstKangaroo==secondKangaroo){ trueFalse = true; break; } } return trueFalse ? "YES" : "NO"; }Lo arrojé a la variable v1 con x1. Hice lo mismo para x2 y v2. Hice que el ciclo continuara hasta 10000. Si x1 + v1 = x2 + v2, entonces debería devolver verdadero, no falso. Mi código se ejecuta sin errores, pero no puede pasar todos los casos de prueba en HackerRank. No puedo encontrar dónde me equivoqué.
Varios asuntos:
firstKangaroo ni secondKangaroo (no saltan), por lo que si en la primera iteración no son iguales, seguirán siendo desiguales en la segunda, tercera, ... y todas las demás iteraciones del ciclo. . Así que el bucle no sirve para nada.Además, esta idea no es eficiente. Mira las matemáticas de este problema:
Si los canguros se encuentran, entonces debe haber una cantidad de saltos k tal que:
x1 + k*v1 == x2 + k*v2Por lo que entonces
(x1 - x2) == k*(v2 - v1) ...y que k debe ser un entero sin signo, es decir, debemos comprobar que (x1 - x2) es un múltiplo de (v2 - v1) . Además, sus signos deben ser los mismos, y luego el resto después de la división debe ser 0; podemos usar el operador % para eso.
Asi que:
function kangaroo(x1, v1, x2, v2) { return Math.sign(x1 - x2) === Math.sign(v2 - v1) && ( v1 === v2 || (x1 - x2) % Math.abs(v2 - v1) === 0) ? "YES" : "NO"; } // Test run: console.log(kangaroo(0, 2, 5, 3)); Como en el desafío del código se da que x1 < x2 podemos simplificar un poco:
function kangaroo(x1, v1, x2, v2) { return v2 < v1 && (x2 - x1) % (v1 - v2) === 0 ? "YES" : "NO"; } // Test run: console.log(kangaroo(0, 2, 5, 3));Un enfoque, diferente del análisis matemático de Trincot, es probar hasta que el canguro que se mueve más rápido esté por delante del más lento, deteniéndose si se encuentran. Si no lo han hecho para entonces, nunca lo harán. Podemos hacer esto con una recursividad bastante simple:
const kangaroo = (x1, v1, x2, v2) => v1 < v2 ? kangaroo (x2, v2, x1, v1) : x1 == x2 ? 'YES' : v1 == v2 ? 'NO' : x1 > x2 ? 'NO' : kangaroo (x1 + v1, v1, x2 + v2, v2) console .log (kangaroo (0, 3, 4, 2)) console .log (kangaroo (0, 2, 5, 3)) Si el más rápido es el segundo, los intercambiamos. Si ya están en el mismo lugar, hemos terminado. Si no, y tienen el salto del mismo tamaño, nunca podrán encontrarse. Si el más rápido está por delante del más lento, nunca se encontrarán. De lo contrario, hacemos un salto (incrementando x1 por v1 y x2 por v2 ) y volvemos a probar.