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 […]

Continue reading →

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 […]

Continue reading →

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- […]

Continue reading →

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 […]

Continue reading →

All about Factorial(!)

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 […]

Continue reading →

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 […]

Continue reading →

Merge Sort

Merge Sort is an example of a divide and conquer algorithm. A Divide and Conquer algorithm solves a problem using following three steps- 1. Divide: Break the given problem into sub-problems of same type. 2. Conquer: Recursively solve these sub-problems. 3. Combine: Appropriately combine the answers. In merge sort,the input array is divided in two […]

Continue reading →