# Minimum Cost Path (DP Example)

Dynamic programming is a method for solving complex problems by breaking them down into simpler sub-problems. It is applicable to problems exhibiting the properties of overlapping sub-problems and optimal substructure.When applicable,the method takes far less time than naive methods that don’t take advantage of the sub-problem overlap. A problem is said to have overlapping sub-problems […]

# Magic Square

A magic square is an arrangement of numbers in a square grid, where the numbers in each row, and in each column, and the numbers in the forward and backward main diagonals, all add up to the same number.A magic square of order N means it has N rows and N columns.It contains all integers […]

# Largest multiple of 3

Given an array of digits,the task is to find the largest multiple of 3 that can be formed from array elements. Example- Input array is {4,8,0}.Then,the largest number formed using these digits and divisible by 3 is 840. Properties of multiples of 3- 1.Sum of the digits of the multiple is divisible by 3. Example- […]

# Fibonacci Numbers

Fibonacci is the most famous sequence in the programming world. It is defined by the following recursive formulation: f(n)=f(n-1) + f(n-2) where f(0)=0 & f(1)=1. The first few numbers of the sequence are: 0,1,1,2,3,5,8,13,21,34,55…… Program to find the N-Th Fibonacci number can be implemented iteratively or recursively very easily.But,for large values of N,we need an […]

In mathematics,the factorial of any positive number N is the product of the positive integers less than or equal to N.It is denoted by ‘N!’. Example- 5!= 5*4*3*2*1 =120 Also,0!=1. In C/C++,no data type can store the value of factorial of a number greater than 20.To find the factorial of greater numbers easily,JAVA/Python can be […]

# Binomial Coefficient

Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial expansion of (1+x)^n.It also represents an entry in Pascals Triangle. Properties- 1. nCk=(n!)/[(k!)*(n-k)!] 2. nCn=1 3. nC0=1 4. nCk=(n-1)C(k)+(n-1)C(k-1) 5. nCk=(n)C(n-k) The task is to find the value […]

# Longest Increasing Sub-sequence

Given a sequence of numbers,we need to find the longest increasing sub-sequence from the given input(not necessary continuous). Example- Input- 1 10 4 5 3 2 9 11 13 Increasing Sub-sequences- 1 4 5 5 9 11 13 10 11 13 4 5 9,etc Longest Increasing Sub-sequence– 1 4 5 9 11 13 Length of […]

# N Queens Problem (Backtracking)

Given a chess board of size n*n,the task is to find all the ways to place n queens so that they don’t attack each other. In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. Naive Algorithm- Backtracking Algorithm- If queens are at (i,j) and (k,l) coordinates,then they can attack […]