memoization

Pascal’s triangle is based on this formula : C(n, r) = C(n-1, r-1) + C(n-1, r) int Pascal(int n, int r) { if (r == 0) return 1; if (n == 0) return 0; return Pascal(n - 1, k - 1) + Pascal(n - 1, r); } In cpp, this recursive routine can use both memoization and recursion: public static long nCr(int n, int r){ static unsigned long table$256$$256$ = {0}; if(r == 0 || n == r) { return table$n$$r$ = 1; } if(r == 1) { return table$n$$r$ = n; } if(r > n / 2) { return table$n$$r$ = ncr(n, n - r); } return table$n$$r$ = table$n - 1$$r - 1$ + table$n - 1$$r$; } In java, you can use a class and maintain the array outside the function and just use the function similar to above to update that array and return the value in the end. [Read More]

Lets look at some solutions. Solution 1 - Using recursion int pow(int x, int y) { if(y == 1) return x ; return x \* pow(x, y-1) ; } Divide and Conquer C program /\* Function to calculate x raised to the power y \*/ int power(int x, unsigned int y) { if( y == 0) return 1; else if (y%2 == 0) return power(x, y/2)\*power(x, y/2); else return x\*power(x, y/2)\*power(x, y/2); } /\* Program to test function power \*/ int main() { int x = 2; unsigned int y = 3; printf("%d", power(x, y)); getchar(); return 0; } Time Complexity: O(n) [Read More]