Fast Exponentiation

Let's see iterative version of x raised to power y in O(log y):

The problem with above solution is, overflow may occur for large value of n or x. Therefore, power is generally evaluated under modulo of a large number.

Efficient way in computing power under modular arithmetic

( Iterative Function to calculate (x^y)%p in O(Log y) ) :

Problem for practice and sample code :

https://www.hackerearth.com/zh/problem/algorithm/modular-exponentiation-c2b26a3b-5ef0a56d/