# Basic Algorithm List

List of few algorithm that come handy. Not that they are super important for interview or anything, but the mainly for knowledge sake.

The idea is simple. At each index of array we check if what’s the maximum subarray till now. The max subarray can be either the current-index-element alone or the sum previous subarray index + the current index.
At each index we check what’s the maximum subarray that we have found instead of storing the sum in another array.
import java.lang.*; -> to use the Math.max collection.
2. Boyer–Moore majority vote algorithm Youtube  Code
Application – Find Majority Element in an Array.
3. Sieve of Eratosthenes – Wiki – Given a number n, print all primes smaller than or equal to n. The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes. Code.
The problem with this algo is the space requirement.
We initially create an array equal to the size of n. Initialize all array index with a false flag. Now start looping through the array starting from i = 2(1 is already prime). We process only i which are marker as false. For each i’s factor mark all the array index as false. This will be a nested loop. Keep doing it till i < =n;
The index left as false are the prime number.
4. Pigeonhole Principle – simple but very helpful in solving many problem. Read few here.
5. Brian Kernighan’s Algorithm – Count set bits in an integer
7. The Lazy Caterer’s Problem – Given an integer n, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making n cuts(pieces can be of unequal size). Wiki
Thus, the total number of pieces after n cuts is