Pregunta de entrevista

Entrevista para Senior Software Engineer

-Buenos Aires


Given three numbers x, y and p, compute (xy) % p. How would you solve the given problem? constrains: avoid overflow, solve in three tries or less


Respuesta de la entrevista

1 respuesta


Use modular arithmetic to compute power. [ (a mod p) (b mod p) ≡ (ab) mod p ] // Calculate (x^n)%p in O(logy) int power(int x, unsigned int y, int p) { // Initialize result int res = 1; // Update x if it is more than or equal to p x = x % p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) { // y must be even now res = (res*x) % p; } // y = y/2 y = y>>1; x = (x*x) % p; } return res; }

Anónimo en

Agregar respuestas o comentarios

Para comentar esto, Inicia sesión o regístrate.