Binary Search

package com.mylearnings;

public class BinarySearch {

public static void main(String[] args) {
int input[] = {5,7,6,8,65,87,12,3,343,44,767,78};
int sortedInput[] = {5,6,12,15,18,25,45,65,70,75,78,80,82,83,85,88,90,98,100,105,107};
BinarySearch search  = new BinarySearch();
int index = search.binarySearch(sortedInput, 0, sortedInput.length, 65);
System.out.println(index);
}

public int binarySearch(int[] input, int startIndex, int endIndex, int search) {
if(startIndex <= endIndex) {

int mid= startIndex + (endIndex - startIndex)/2;
int midVal = input[mid];
if(midVal == search) {
//System.out.println("Value found at index : "+mid);
return mid;
}else if(search < midVal) {
return binarySearch(input, startIndex , mid-1, search);
}else {
return binarySearch(input, mid+1, endIndex, search);
}
}

return -1;
}

}

Inefficient O(n^2) Method of finding Largest Recurring Substring in a string

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* @author Pragya Rawal
*/
public class LargestSubstring {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter String : ");
try {
String input = br.readLine();
LargestSubstring str = new LargestSubstring();
String largestSubstr = str.getLargestSubstr(input);
if (largestSubstr != null) {
System.out.println("Largest Recurring substring is : "
+ largestSubstr);
}
} catch (IOException e) {
e.printStackTrace();
}

}

public String getLargestSubstr(String input) {
if (null == input || input.length() == 0) {
System.out.println("Invalid / Empty string ...");
return null;
} else {
int length = input.length();
int subStrLen = 0;
String longestSubStr = "";
String currentStr = "";
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
int k = i;
int l = j;
while ((k < length) && (l < length) &&(input.charAt(k) == input.charAt(l)) ) {
currentStr += input.charAt(k);
k++;
l++;
subStrLen++;
}
if (longestSubStr.length() < currentStr.length()) {
longestSubStr = currentStr;
}
currentStr = "";
}

}
return longestSubStr;
}

}
}

Program(s) for finding power of a number

First, an interactive solution: (raising a to the power of b)

public double Power(double a, int b) {
if (b<=0) return 0; // we want a positive integer for the exponent
else {
double c=1;
for (int i=0; i c*=a;
}
return c;
}
}


Very easy and linear. You start from one and go on multiplying c by a so c is respectively 1, a, a^2, a^3, ... a^b.
When done, you return c. This one takes linear time.

Second, a recursive solution:

public double Power(double a, int b) {
if (b<=0) return 0;
else if (b==1) return a;
else {
return a*Power(a,b-1);
}
}


This is also an easy one. What we do here? Simple: we calculate a^b=a * a^(b-1). This is done by the recursion and takes linear time as well.

So, how can we beat these to slugs? We do this way.
Let me give you an example with b being a power of 2 (which is the easiest to understand).

Imagine you have to evaluate a^64. You could think this:

a^64 = c^32 where c=a^2
c^32 = d^16 where d=c^2
d^16 = e^8 where e=d^2
e^8 = f^4 where f=e^2
f^4 = g^2 where g=f^2
g^2 = g*g

This requires 6 operations. Using one of the two previous algorithms takes 64 operations! In fact 6=log64 (log is meant in base 2 obviously).

Now, things are different when b isn't a power of 2, but the algorithm is just a bit more complicated. Let's see an example again. We'll evaluate a^20.

a^20 = c^10 where c=a^2
c^10 = d^5 where d=c^2
d^5 = d * e^2 where e=d^2
e^2 = e*e

This requires 5 operations. Log16=4 and log32=5 so as you can see we have here 5=Ceiling(log20). This happens when b isn't a power of 2, but the cost of the entire algorithm doesn't grow that much and we can still say that it runs in logarithmic time (this is more true when b is a medium-big number).

private double Power(double a, int b) {
if (b<0) {
throw new ApplicationException("B must be a positive integer or zero");
}
if (b==0) return 1;
if (a==0) return 0;
if (b%2==0) {
return Power(a*a, b/2);
} else if (b%2==1) {
return a*Power(a*a,b/2);
}
return 0;
}


Another solution can be :
a^b = 10^(ln[10](a) * b)

Reference : http://www.osix.net/modules/article/?id=696

My Hanoi Prog

public class TowerOfHanoi {

static int moves = 0;
public static void main(String[] args) {
char fromPole = 'A';
char toPole = 'B';
char withPole = 'C';
hanoi(3, fromPole, toPole, withPole);
}
public static void hanoi(int height , char fromPole , char toPole , char withPole){
if(height >= 1){
hanoi(height - 1, fromPole, withPole ,toPole);
move(fromPole , toPole);
hanoi(height - 1,withPole,toPole , fromPole );
}
}
public static void move(char fromPole , char toPole){
moves++;
System.out.println("****Next Move****");
System.out.print(fromPole+ "-->");
System.out.println(toPole);
}
}


Output is :
****Next Move****
A-->B
****Next Move****
A-->C
****Next Move****
B-->C
****Next Move****
A-->B
****Next Move****
C-->A
****Next Move****
C-->B
****Next Move****
A-->B

Java Program for Tower of Hanoi problem (Very Simple and Easy solution)

This program implements the ``classical'' recursive algorithm that solves the Towers of Hanoi problem. The recursive algorithm is based on the observation that moving a tower of height h from pole A to pole B is equivalent to moving a tower of height h-1 to pole C, them moving the last disk from pole A to pole B, and finally moving the the tower from pole C to B. So the problem of moving a tower of height h, has been reduced to the one of moving a tower of height h-1.
The following Java application uses only one class variable, moves, which holds the number of moves so far. The variable is used only for formating purposes.

<*>=

import java.io.*;

public class hanoiA
{
static int moves=0; //number of moves so far




}

This code is written to a file (or else not used).
Method getInt is used to read an integer from the user terminal. The method is based on the new API therefore the whole program cannot be executed with an old JDK. Its functionality is very simple: it reads an input line which is supposed to contain only one integer. If the line contains what should contain it transforms the line into a valid integer and return it, otherwise it returns the number 1 and print an error message.

=
static int getInt()
{
String line;
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
try
{
line = in.readLine();
int i = Integer.valueOf(line).intValue();
return i;
}
catch (Exception e)
{
System.err.println("***Error: Input is not a number.\n" +
"Input assumed to be the number 1");
return 1;
}
}

Used above.
Method hanoi is the kernel of the program---it ``performs'' the moves. It accepts four arguments: the height of the current tower, the fromPole, the toPole and the withPole. Initially the tower has height, say n. Then we must move a tower of height n-1 from fromPole to withPole, move the biggest disk from fromPole to toPole and finally move the tower of height n-1 to pole toPole from withPole. The first step is implemented as a call to the method itself (procedures are called methods in Java), the second to a call to method moveDisk, and finally the third step to a call to the itself. Particularly, the withPole is the pole we move the tower of height n-1.

Each recursive method must have a termination condition, i.e., a condition that signals the termination of the method, or else it will never terminate! In our case this condition is reached when the height of the tower is zero.

=
static void hanoi(int height,
char fromPole,
char toPole,
char withPole)
{
if (height >= 1)
{
hanoi(height-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
hanoi(height-1, withPole, toPole, fromPole);
}
}

Used above.
Method moveDisk simply print on the terminal each move. A ``move'' is defined by the orientation pole and the destination pole, each represented by a character. The method prints a string of the form ``FT'' where ``F'' denotes the orientation pole and ``T'' the destination pole. Moreover, it tries to make the output readable. So, it prints only twenty moves per line, by detecting multiples of the number 20.

=
static void moveDisk(char fromPole, char toPole)
{
moves++;
System.out.print(fromPole);
System.out.print(toPole);
System.out.print(((moves % 20)==0) ? '\n' : ' ');
}

Used above.
Method main is there where the whole action is. The first thing is to define the poles as characters and to the height of the tower as an integer. Next, it reads the height of the tower (in case we type some rubbish or a negative number, the height is assumed equal to 1). Finally, it prints out the solution. The last aspect of this program is that it print its execution time in milliseconds.

=
public static void main(String[] args)
{
long time1, time2; //for benchmarking
int TowerHeight;
char FromPole='A', ToPole='B', WithPole='C';

System.out.println("Enter Tower height...");
System.out.print("?");
TowerHeight = getInt();
time1 = System.currentTimeMillis();
hanoi(TowerHeight, FromPole, ToPole, WithPole);
time2 = System.currentTimeMillis();
System.out.println();
System.out.print(time2-time1); //print execution time in msec
System.out.println(" msec execution time");
}

Given a positive number, write a prog to find next multiple of 8

public class NextMultipleOfEight {

public static void main(String[] args) {
int x = 22;
System.out.println((x/8+1) << 3);
}

}

BFS prog for the Graph in the last blog

public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2;
while( !theQueue.isEmpty() ) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
{ // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.insert(v2); // insert it
} // end while
} // end while(queue not empty)
// queue is empty, so we're done
for(int j=0; j< totalVertices; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()

Complete + Easy + My MergeSort

public class MyMergeSort {

/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 14, 23, 76, 32, 76, 12, 11, 90 };
mergeSort(arr , 0 ,arr.length);
for(int i = 0 ; i < arr.length ; i ++){
System.out.println(arr[i]);
}
}

public static void mergeSort(int[] input , int firstIndex , int lastIndex){
int leftHalfSize;
int rightHalfSize;
if(lastIndex > 1){
leftHalfSize = lastIndex / 2;
rightHalfSize = lastIndex - leftHalfSize;

mergeSort(input, firstIndex, leftHalfSize);
mergeSort(input, firstIndex + leftHalfSize, rightHalfSize);

merge(input , firstIndex , leftHalfSize , rightHalfSize);
}

}
public static void merge(int[] input , int firstIndex , int leftHalfSize , int rightHalfSize){
int[] temp = new int[leftHalfSize + rightHalfSize];

int[] leftArray = new int[leftHalfSize];
int[] rightArray = new int[rightHalfSize];

for(int i = 0 ; i < leftHalfSize ; i++){
leftArray[i] = input[firstIndex + i];
}
for(int j = 0 ; j < rightHalfSize ; j++){
rightArray[j] = input[firstIndex + leftHalfSize + j ];
}
int i = 0 , j = 0 ,k = 0;
for(; i < leftHalfSize && j < rightHalfSize ;){
if(leftArray[i] < rightArray[j]){
temp[k] = leftArray[i];
i++;
k++;
}else{
temp[k] = rightArray[j];
j++;
k++;
}
}
if(i < leftHalfSize){
while (i < leftHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = leftArray[i];
k++;
i++;
}
}

if(j < rightHalfSize){
while (j < rightHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = rightArray[j];
k++;
j++;
}
}
for(int m = 0 ; m < leftHalfSize + rightHalfSize ; m++){
input[firstIndex+ m ] = temp[m] ;
}
}

}

Merge Sort -> Complete Prog

public class MergeSort
{
private int a[];

public MergeSort(int b[])
{
a = b;
}
public void sort()
{
if(a.length <= 1)
return;
int first[] = new int[a.length / 2];
int second[] = new int[a.length - first.length];
for(int x = 0; x < first.length; x++)
first[x] = a[x];
for(int x = first.length, y = 0; x < a.length; x++, y++)
first[y] = a[x];
//Split the array again
MergeSort sort1 = new MergeSort(first);
MergeSort sort2 = new MergeSort(second);
sort1.sort();
sort2.sort();

merge(first, second);
}
private void merge(int first[], int second[])
{
int x = 0;
int y = 0;
int z = 0;
while(x < first.length && y < second.length)
{
if(first[x] < second[y])
{
a[z] = first[x];
x++;
}
else
{
a[z] = second[y];
y++;
}
z++;
}
//copy remaining elements to the tail of a[];
for(int i = x; i < first.length; i++)
{
a[z] = first[i];
z++;
}
for(int i = y; i < second.length; i++)
{
a[z] = second[i];
z++;
}
}
}

Merge Sort -> Merge + MergeSort

public static int[] merge(int[] a, int[] b){
int len1 = a.length;
int len2 = b.length;
int[] c = new int[len1 + len2];
int len = len1 < len2 ? len1 : len2;
int i = 0 , j = 0 , k = 0;
for(; i < len1 && j < len2 && k < len1 + len2 ; ){
if(a[i] < b[j]){
c[k] = a[i];
k++;
i++;
}else{
c[k] = b[j];
k++;
j++;
}
}

if(i < len1){
while (i != len1 || k != len1 + len2){
c[k] = a[i];
k++;
i++;
}
}

if(j < len2){
while (j != len2 || k != len1 + len2){
c[k] = b[j];
k++;
i++;
}
}

return c;
}

Stable Sort

• A sort is stable if the order of elements with the same key is retained.

Insertion Sort

public static int[] insertionSort(int[] arr){
int len = arr.length;
for(int i = 0 ; i < len ; i++){
for(int j = 0 ; j < i ; j++){
if(arr[i] < arr[j]){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;

}
}
}

return arr;
}

Selection Sort

public static int[] selectionSort(int[] arr){
int len = arr.length;

for (int i = 0 ; i < len ; i++){
int min = arr[i];
for(int j = i + 1 ; j < len ; j++){
if(min > arr[j]){
int temp = arr[j];
arr[j] = min;
min = temp;
arr[i] = min;
}
}

}
return arr;
}

Bubble Sort

public static int[] bubbleSort(int[] arr) {
int len = arr.length;

for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}

Better method to find subarray with largest sum

static int maxSubArray2(int array[], int size)

{
int maxsofar = 0;
int currentmax = 0;
for (int i = 0; i < size; i++)
{
currentmax = (currentmax + array[i] > 0) ? currentmax + array[i]
: 0;
maxsofar = (maxsofar > currentmax) ? maxsofar : currentmax;
}
return maxsofar;

}

Program to find Subarray having maximum sum in a given integer array

public static void findSubarray(int[] arr){
int len = arr.length;
int largest = 0;
int lowerBound = 0;
int upperBound = 0;
for(int i = 0 ; i < len ; i++){

int sum = arr[i];
for(int j = i+1 ; j < len ; j++){
sum += arr[j];
if(sum > largest){
largest = sum;
lowerBound = i;
upperBound = j;
}
}
}
System.out.println("Largest sum is : "+largest );
System.out.println("Largest subarray is between "+arr[lowerBound]+ " and "+arr[upperBound]);

}

Program to find nth power of a given number

public static long findPower(long x , long pow){
if(pow == 1){
return x;
}else if(pow == 0){
return 1;
}else {
return x*findPower(x, --pow);
}
}

Good Prog : Exchanging values with xor

x = x ^ y;
y = x ^ y;
x = x ^ y;

Bitwise operations

Use: Shift left multiplies by 2; shift right divides by 2

y = x << 3; // Assigns 8*x to y.
y = (x << 2) + x; // Assigns 5*x to y.

Find max of three numbers using ternary operator

int a = 5;
int b = 10;
int c = 25;

int result = (a > b) ? ((a > c) ? a : c): ((b > c) ? b : c );

System.out.println(result);