## Google Interview Question

Web Developers**Team:**Solutions Engineering Team

**Country:**United States

**Interview Type:**Phone Interview

```
/**
* @brief Generates a random integer
* @return A random positive integer or a zero
*/
int getRandom()
{
/* Three large prime numbers */
/*Refer to compoasso.free.fr/primelistweb/page/prime/liste_online_en.php */
int a = 1000003;
int b = 2000003; // b = 2*a or closest prime number
int c = 3000017; // c = 3*a or closest prime number
static int seed = 5;
int newSeed = ((a * seed) % c + b) % c;
if(newSeed < 0)
{
newSeed += c;
}
if(newSeed == seed) // IS IT POSSIBLE ?? I DO NOT KNOW HOW TO PROVE/DISPROVE IT.
{
std::cout << "\nREPETITION FOUND !! " << seed << "\n";
seed += a;
/*Explanation for above step
* We are effectively doing the operation y = (ax + b) mod c, where a, b, c are primes
* Suppose we get some bad case when y = x [IS IT POSSIBLE ?? I DO NOT KNOW]
* That implies (ax + b) mod c = x
* Now, what if we replace x with (x + a) ? Will we still get x yet again ? NO
* PROOF : Let (ax + b) mod c = x
* To prove : It is impossible that (a(x + a) + b) mod c = x
* If above is possible, we can equivalently say
* (ax + a*a + b) mod c = x
* or, {(ax + b) mod c + (a*a) mod c} mod c = x
* or, {x + a*a} mod c = x
* This is possible if and only if (a*a) is a multiple of c, which is IMPOSSIBLE because
* a != c, and both a and c are primes
* So, the logic of adding a to seed will definitely ensure that
* we do not get seed again in very next iteration
* */
}
else
seed = newSeed;
return seed;
}
/**
* @brief Generates a positive random integer in the range min to max
* @param min Lower limit
* @param max Upper limit
* @return A random positive integer
*/
int getRandom(int min, int max)
{
if(min < 0 || max < 0 || min > max)
throw "min must be strictly less than max";
if(min == max)
return min;
else
{
int diff = max - min;
return min + getRandom() % (diff + 1);
}
}
```

Use shiftxor algorithm to generate a random number:

- PenChief September 15, 2017