Google Interview Question Software Engineer / Developers
1of 1 votecalculate (x^y)%z without pow();
Team: youtube
Country: United States
Interview Type: Phone Interview
People are missing the point that this is modular exponentiation and you got it right my friend +1. Your program works fine, but I suggest you use the code formatter next time, I think that's why people don't understand the code.
This is a nice implementation from the book Applied Cryptography by Bruce Schneier.
Nicely explained here: ht p://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers
C Version
int NoPowMod( int x, int y, int z )
{
int a = x % z;
int t = 1;
while( y > 0 )
{
// Y is odd
if( y & 1 )
{
t = (t * a) % z;
}
y >>= 1;
a = (a * a) % z;
}
return(t);
}
int calcp(int x,int y,int z)
{
int t = 1;
for(int j = 0;j< y;j++)
{
t = (t*x)%z;
}
return t;
}
Just as a brief explanation, the part of (t*x) that gets thrown away by the % operator value is divisible by the % operator value, so multiplying that value further will always give evenly divisible multiples, so you can just remove it.
Since the modulo operation is distributive, we can reduce the overflow chances further as below
int calp(int x,int y,int z)
{
int t = 1;
x = x % z;
for(int j = 0;j< y;j++)
{
t = (t*x)%z;
}
return t;
}
Hint : (ab) mod n = ((a mod n) (b mod n)) mod n.
The following is a O(logn) based algorithm to compute the power. We can just do:
power(x,y)%z
public static int power(int x, int n) {
if(n == 0)
return 1;
else if(n==1)
return x;
else if(n%2==0) {
int y = power(x,n/2);
return y*y;
}else {
int y = power(x,n-1/2);
return y*y*x;
}
}
The line:
int y = power(x,n-1/2);
is incorrect "/" takes precedence before "-", so the expression n-1/2 will actually evaluate to n. Btw, since n is odd you could just write n/2 (it will truncate the result, and it is equivalent to (n-1)/2).
Also, your solution will likely overflow since x^y can easily get over 2^31-1. You need to apply "% z" to each multiplication inside the power() function.
What if x and z are very large, like 2^31-10? Even if you use "% z" for each multiplication it is not ok, for example x*x will overflow. So, when performing a multiplication you need to use long long ints (which can hold numbers up to 2^63-1). For example, line "return y*y" should be "return ((long long)y * y) % z"
For a correct implementation, which also works for large int values for x, y, z check my answer.
@loveCoding
See cristian.botau comment. The idea of computing a % implies handling of overflows. Computing an exponential first and then taking modulus later will not give correct results for large x and y,
what you have done is definitely log(n) solution but it will make integer overflow very easily as x^n will easily cross integer max limit.
It could be safely done in below steps, not crossing integer overflow limit.
using the formula (ab) mod n = ((a mod n)*(b mod n)) mod n
public int getMod(int x, int y, int z){
if(y == 1)
return x%z;
int halfMod = ((getMod(x, y/2, z)%z) * getMod(x, y/2,z))%z;
if (y%2 == 0){
return halfMod;
}else {
return ((halfMod%z)*(x%z))%z;
}
}
It is O(logY) complexity and will never cross integer max limit.
Here is an O(log(y)) algorithm. It is the classical fast exponential algorithm. I won't get into details into it because it is a simple algorithm and can be found easily by googling it.
However, the trick to this problem is to watch out for arithmetical overflows:
- since x^y can grow really big, you can't just compute x^y and then apply % z, since it will likely overflow; so you need to apply modulo z operation on each multiplication;
- furthermore for high values of z even one multiplication can overflow (take for instance x = 2 billions - 1, y = 2, z = 2 billions), so you need to use the long long type for each multiplication;
In order to make sure there is no arithmetic overflow happening, I've defined the modMul(x, y, z) operation which performs the operation "(x * y) % z" and guarantees there is no overflow.
inline int modMul(int x, int y, int z) {
int result = ((long long)x * y) % z;
return result;
}
int power(int x, int y, int z) {
if (y == 0)
return 1;
int sqrt = power(x, y / 2, z);
int result = modMul(sqrt, sqrt, z);
if (y % 2 == 1)
result = modMul(result, x, z);
return result;
}
public static int theCode(int x, int y, int z)
{
int temp = x;
for (int i = 1; i <= y; i++)
{
x = x * temp;
}
return x % z;
}
(int) exp(y * log(x)) % z
#include <iostream>
#include <cmath>
static int pow_exp_log(int x, int y) {
return ((int) exp(y * log(x)));
}
int main() {
int x = 3, y = 4, z = 5;
std::cout << "exp(y * log(x)) % z = " << pow_exp_log(x, y) % z << std::endl;
std::cout << "pow(x, y) % z = " << (int) pow(x, y) % z << std::endl;
}
So far no one has handled the case where y is a negative integer.
float func(int x, int y, int z) {
float temp = 1;
for(int i = y; i > 0; i--) {
temp *= x;
}
if(y < 0) {
temp = 1 / x;
}
return temp % z;
}
That's because it doesn't make sense in modular arithmetic (floating point numbers don't make much sense in modular arithmetic).
Actually, it would make sense if you would compute the modular multiplicative inverse of x^abs(y) if y is negative, but that can be computed only if x^abs(y) and z are coprimes (so the problem might not always have an answer).
/**
* Computes (x^y) % z, without using power function in O(log y) time.
* Uses distributive property of modulo function: (a*b) % c = ((a%c) * (b%c)) % c
* To compute (x^y) % z, first recursively calls itself compute to (x ^ (y/2)) % z,
* then uses this value to compute (x ^ y) % z, by appropriately squaring, etc.
* @param x
* @param y
* @param z
* @return
*/
public static int CalculatePowerModulo(int x, int y, int z)
{
int factor = x % z;
if (y == 1)
{
return factor;
}
int value1 = CalculatePowerModulo(x, y/2, z);
int value2;
if (y % 2 == 0)
{
value2 = value1;
}
else
{
value2 = (factor * value1) % z;
}
return (value1 * value2) % z;
}
#include<stdio.h>
#include<stdlib.h>
long int power(long int x,long int y,long int z);
int main()
{ long int x=2;
long int y=10;
long int z=200000;
printf("%ld",power(x,y,z));
return 0;
}
long int power(long int x,long int y,long int z)
{ long int k;
if(y==0)
return 1;
if(y==1)
return x%z;
if(y%2==0)
{ k=power(x,y/2,z);
k=k%z;
return((k*k)%z);
}
else
{k=power(x,y/2,z);
k=k%z;
k=(k)%z;
x=x%z;
return((k*k*x)%z);
}
#include<stdio.h>
#include<stdlib.h>
long int power(long int x,long int y,long int z);
int main()
{ long int x=2;
long int y=10;
long int z=200000;
printf("%ld",power(x,y,z));
return 0;
}
long int power(long int x,long int y,long int z)
{ long int k;
if(y==0)
return 1;
if(y==1)
return x%z;
if(y%2==0)
{ k=power(x,y/2,z);
k=k%z;
return((k*k)%z);
}
else
{k=power(x,y/2,z);
k=k%z;
k=(k)%z;
x=x%z;
return((k*k*x)%z);
}
}
}
Hint : (ab) mod n = ((a mod n) (b mod n)) mod n.
Time Complexity: O(logb) for a^b;
the question here is how we can reduce the complexity... if we compute the x^y by normal method the complexity is O(y)... to reduce the complexity we can use binary weighted power computation method in which complexity is O(logy)..
- Anonymous July 24, 2013ans=1; square=x; if(y==0) return 1; while(y!=0) { if(y%2) ans=ans*square; square=(square*square)%z; y=y/2; if(ans>z) ans=ans%z; } return ans;