## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 8 vote

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)..

``````ans=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;``````

Comment hidden because of low score. Click to expand.
3

here in each step mod z is used just to prevent overflow for large x or y...

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

thanks oOZz...

Comment hidden because of low score. Click to expand.
0

Could somebody please format the code and explain?

Comment hidden because of low score. Click to expand.
0

Here complexity is O(log y) not O(y); because we are reducing y to half in every iteration

Comment hidden because of low score. Click to expand.
2
of 2 vote

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);
}``````

Comment hidden because of low score. Click to expand.
0

what if y equals to zero

Comment hidden because of low score. Click to expand.
1
of 9 vote

``````int calcp(int x,int y,int z)
{
int t = 1;
for(int j = 0;j< y;j++)
{
t = (t*x)%z;
}
return t;
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
2

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.``````

Comment hidden because of low score. Click to expand.
0

Why do you need z

Comment hidden because of low score. Click to expand.
1
of 3 vote

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;
}
}``````

Comment hidden because of low score. Click to expand.
0

The question clearly mentions not to use pow()

Comment hidden because of low score. Click to expand.
0

Akbar-The-Slave, The emperor has written his own power method.

Comment hidden because of low score. Click to expand.
0

See the code below its much more simpler.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@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,

Comment hidden because of low score. Click to expand.
0

``````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.``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}

Comment hidden because of low score. Click to expand.
0

Will not work when y = 1

Comment hidden because of low score. Click to expand.
0
of 0 vote

(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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0
of 0 vote

``it means u cannot first use pow(x,y) and then mod it by z . i guess.``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int count(int x, int y, int z)
{
int temp_x = x;
int temp_y = 1;
while(temp_y<y)
{
++temp_y;
x *= temp_x;
}
return x %= z;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can eliminate % by doing:

``````int result=1;
int i;

for(i=0;i<y;i++)
result=result*x;
while(result>=z)
result-=z;

printf("\n%d\n",result);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* 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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

principle: （a*b）mod n = ((a mod n)*(b mod n)) mod n
Apply: （a*a*a*a*a*a*）mod n = (((a*a)mod n)((a*a)mod n)((a*a)mod n)*(x mod n))mod n
SO, Code is;
int pow(int x, int y, int mod)
{
int res = 1;
while(y)
{
if(y & 1) res = res * x % mod;
x = x * x % mod;
y = y / 2;
}
return res;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int compute(int x, int y, int z) {
int r = x % z;
for (int i=0; i< y-1; i++) {
r = r * x;
r = r % z;
}
return r;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````ans = 1;
while(y>0)
{
while(y%2==0)
{p = ((p%z)*(p%z))%z;
y/=2;
}
ans = (ans*p)%z; y--;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

long long int pw(long long int a, long long int b,long long int ma)
{

long long int ans=1;
while(b)
{
if(b&1)ans=ans*a%ma;
b>>=1;
a=a*a%ma;
}
return (ans+ma)%ma;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````long long int pw(long long int a, long long int b,long long int ma)
{

long long int ans=1;
while(b)
{
if(b&1)ans=ans*a%ma;
b>>=1;
a=a*a%ma;
}
return (ans+ma)%ma;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````long long int pw(long long int a, long long int b,long long int ma)
{

long long int ans=1;
while(b)
{
if(b&1)ans=ans*a%ma;
b>>=1;
a=a*a%ma;
}
return (ans+ma)%ma;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is there any better solution that O(log(n)) ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.