Write a program to find (x^y) % z

Question

pf · Accepted Answer

I guess the point is how to avoid overflow. Good algorithms for this does not lead to overflow and return the correct answer; normal ones may easily lead to overflow.

Vivek · Answer

I guess we need to use Congruences from Number theory here

Yingsheng Gao · Answer

I think there is some point we need to check.
first will x be negative? If so, we need to handle this problem
In addition, in the case y is very large, a O(y) algorithm is not a good idea, we might need to use the O(lg Y) one.

Paul Orlov · Answer

result = x mod z

for i = 2 to y do result = (result * x) mod z

Nipun · Answer

(x ^ y) % z  
is equal to:
(x << (y-1)) % z

Google

Domanda di colloquio di Google

Risposte di colloquio

Aziende seguite

Ricerche di lavoro