// Find the GCD of integers a and b
int gcd(int a, int b)
{
int t;
while ( b > 0 )
{
a %= b;
t = a;
a = b;
b = t;
}
return a;
}
Modular Exponentiation
// Calculate m^e % n
int bigmod(int m, int e, int n)
{
long long ans, base; base = m; ans = 1;
// loop until e = 0 (binary conversion)
while ( e > 0 )
{
// if e is odd, remainder with 2 is 1 (binary conversion)
if ( e & 1 )
{
// if the LSB of e in binary is 1, multiply the answer with current base
ans *= base;
if ( ans >= n )
{
ans %= n;
}
}
// divide e with 2 (binary conversion)
e >>= 1;
// calculate base^2n = base^n * base^n
base *= base;
if ( base >= n )
{
base %= n;
}
}
return (int)ans;
}
Fibonacci number(fast method)
// Fibonacci by Matrix O(log n)
int Divide_Conquer_Fib(int n)
{
int i,j,k,h,t;
i = h = 1;
j = k = 0;
while (n > 0)
{
if (n & 1)
{
t = j*h;
j = i*h + j*k + t;
i = i*k + t;
}
t = h*h;
h = 2*k*h + t;
k = k*k + t;
n >>= 1;
}
return j;
}
nCr for big result
// nCr for big result ( result < 2^31 )
// the gcd() inside should be written by long long type
long long big_ncr(int n, int r)
{
int up, down, u, d, i, t;
up = down = 1;
if ( r > (n >> 1) ) r = n - r;
for ( i = r; i >= 1; --i )
{
u = n-r+i;
d = i;
t = gcd(u,d);
u /= t; d /= t;
t = gcd(up,d);
up /= t; d /= t;
t = gcd(down,u);
down /= t; u /= t;
up *= u;
down *= d;
}
return (up / down);
}
Josephus problem
/*
Assume the numbering is started from 0, e,g {0,1,2,3,4,5,6,7,......}
and eliminate one by one, then ( new id + m ) % n = old id
i.e. ( P(n-1,m) + m ) % n = P(n,m)
Since we wanted to find the one who lived, so P(1,n) = 0, loop upwards
*/
// Josephus problem, return who will be alive
int joseph(int n, int m)
{
int i, c = 0;
for ( i = 2; i <= n; ++i )
{
c += m;
c %= i;
}
return c + 1; // count from 1;
}
// Return centroid of polygon
void Centroid_Poly(double X[], double Y[], int nPt, double &cx, double &cy) {
int i;
double AX, AY, AA, temp;
temp = X[nPt-1]*Y[0] - X[0]*Y[nPt-1];
AA = temp;
AX = (X[nPt-1]+X[0]) * temp;
AY = (Y[nPt-1]+Y[0]) * temp;
for (i=0;i<nPt-1;i++) {
temp = X[i]*Y[i+1] - X[i+1]*Y[i];
AA += temp;
AX += (X[i]+X[i+1])*temp;
AY += (Y[i]+Y[i+1])*temp;
}
AA/=2;
cx = AX/6/AA;
cy = AY/6/AA;
}
String
Edit Distance
int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
// d is a table with lenStr1+1 rows and lenStr2+1 columns
declare int d[0..lenStr1, 0..lenStr2]
// i and j are used to iterate over str1 and str2
declare int i, j, cost
for i from 0 to lenStr1
d[i, 0] := i
for j from 0 to lenStr2
d[0, j] := j
for i from 1 to lenStr1
for j from 1 to lenStr2
if str1[i] = str2[j] then cost := 0
else cost := 1
d[i, j] := minimum(
d[i-1, j ] + 1, // deletion
d[i , j-1] + 1, // insertion
d[i-1, j-1] + cost // substitution
)
return d[lenStr1, lenStr2]
Graph
Dynamic Programming
Coin Change
int count[];
int value[];
for ( i = 0; i < value_count; ++i )
{
for ( j = value[i]; j<=total; ++j )
{
count[j] += count[j-value[i]];
}
}