abhishekprateek
BAN USER/**
* 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;
}
Maximum number of $1 bills you can use n1 = x
Maximum number of $2 bills you can use n2 = x/2
Maximum number of $5 bills you can use n5 = x/5
Maximum number of $10 bills you can use n10 = x/10
Create a set A = { n1 times 1, n2 times 2, n5 times 5, n10 times 10 }
Now the problem reduces to finding number of subsets of A whose sum is exactly x, which is the subset sum problem solvable by dynamic programming.
I think the solution with best run time O(n) is mentioned at stack overflow (answer by Grigor):
- abhishekprateek July 28, 2013