Printing Prime numbers

public class PrimeDemo{

          public static void main(String args[]) {

                    System.out.println("Is 10 prime? : "+isPrime(10));

                    System.out.println("Is 0 prime? : "+isPrime(0));

                    System.out.println("Is 5 prime? : "+isPrime(5));

                    System.out.println("Is 101 prime? : "+isPrime(101));

                    System.out.println("Is 4 prime? : "+isPrime(4));

                    System.out.println("Is 47 prime? : "+isPrime(47));

                    System.out.println("Is 50 prime? : "+isPrime(50));

                    System.out.println("Is 100 prime? : "+isPrime(100));

                    printPrime(11, 23);

}

/**

* printPrime() will print all the prime numbers between start number and end number

* @param start

* @param end

*/

private static void printPrime(int start, int end) {

          System.out.println("Prime numbers between "+start+" & "+end);

          if(start > end){

                    System.out.println("Not valid range");

          }

          else{

                    boolean isPrint = false;

                    for(int i = start; i<=end; i++){

                              for (int j = 2; j <i; j++) {

                                        if(i % j == 0){

                                                isPrint = false;

                                                break;

                                       }else{

                                                isPrint = true;

                                       }

                               }

                               if(isPrint){

                                     System.out.print(" "+i);

                               }

                      }

                 }

    }

/**

* returns true if a number is prime

* @param n

* @return

*/

public static boolean isPrime(int n){

          if (n <= 0){

              return false;

          }

          boolean retVal = true;

         for(int i = 2; i< n; i++){

              if(n % i == 0){

                     retVal = false;

              }

         }

         return retVal;

     }

}

BubbleSort

public void bubbleSort(int[] a) {

         System.out.println("Input Array:");

         for (int i = 0; i < a.length; i++) {

                  System.out.print("  "+a[i]);

         }

         System.out.println();

         for (int p = 0; p < a.length; p++) {

                  for (int i = 0, j = 1; i < a.length && j < a.length; i++, j++) {

                           System.out.print("comparing "+a[i]+" & "+a[j] +"   ");

                            if(a[i] > a[j]){

                                     int tmp = a[i];

                                    a[i] = a[j];

                                    a[j] = tmp;

                           }

         

                           for (int k = 0; k < a.length; k++) {

                                  System.out.print("  "+a[k]);

                           }

                           System.out.println();

                  }

         }

         

         System.out.println("Array is sorted:");

         for (int i = 0; i < a.length; i++) {

                  System.out.print("  "+a[i]);

         }

}

OutPut:

Input Array:

  3  2  5  7  1  12

comparing 3 & 2     2  3  5  7  1  12

comparing 3 & 5     2  3  5  7  1  12

comparing 5 & 7     2  3  5  7  1  12

comparing 7 & 1     2  3  5  1  7  12

comparing 7 & 12     2  3  5  1  7  12

comparing 2 & 3     2  3  5  1  7  12

comparing 3 & 5     2  3  5  1  7  12

comparing 5 & 1     2  3  1  5  7  12

comparing 5 & 7     2  3  1  5  7  12

comparing 7 & 12     2  3  1  5  7  12

comparing 2 & 3     2  3  1  5  7  12

comparing 3 & 1     2  1  3  5  7  12

comparing 3 & 5     2  1  3  5  7  12

comparing 5 & 7     2  1  3  5  7  12

comparing 7 & 12     2  1  3  5  7  12

comparing 2 & 1     1  2  3  5  7  12

comparing 2 & 3     1  2  3  5  7  12

comparing 3 & 5     1  2  3  5  7  12

comparing 5 & 7     1  2  3  5  7  12

comparing 7 & 12     1  2  3  5  7  12

comparing 1 & 2     1  2  3  5  7  12

comparing 2 & 3     1  2  3  5  7  12

comparing 3 & 5     1  2  3  5  7  12

comparing 5 & 7     1  2  3  5  7  12

comparing 7 & 12     1  2  3  5  7  12

comparing 1 & 2     1  2  3  5  7  12

comparing 2 & 3     1  2  3  5  7  12

comparing 3 & 5     1  2  3  5  7  12

comparing 5 & 7     1  2  3  5  7  12

comparing 7 & 12     1  2  3  5  7  12

Array is sorted:

  1  2  3  5  7  12

Reverse a String

Reverse a String
Solution: String can be reversed by 3 ways (which I know)-

1. Using Stack

private static String reverseUsingStack(String str) {

          String revStr = "";

          Stack stk = new Stack();

          char [] chrArr = str.toCharArray();

          for (int i = 0; i < chrArr.length; i++) {

                    stk.push(chrArr[i]);

          }

          

          for (int i = 0; i < chrArr.length; i++) {

                    revStr = revStr + stk.pop();

          }

          return revStr;

}

2. Using StringBuilder

private static String reverseUsingBuilder(String str) {

          StringBuilder bld = new StringBuilder();

          for (int i = str.length() -1; i >=  0; i--) {

                    bld.append(str.charAt(i));

          }

          return bld.toString();

}

3. Using Recursion

private static String reverseUsingRecursion(String str) {

          String rev = "";

          if (str.length() < 2){

                    rev = str;

          }else{

                    rev = reverseUsingRecursion(str.substring(1)) + str.charAt(0);

          }

          return rev;

}

Q. How to find middle element of singly linked list in one pass?

Ans: 

1. You have head (and  tail, which is not required)

2.  Take two pointers tmp1, tmp2 and initialize them to head

3. Iterate through the list, increment tmp1 in each iteration and increment tmp2 after every 2nd interation

4. When tmp1 reaches end of list, tmp2 should have reached middle element of the list

package cs.iit.edu.ds.question;

public class DSQuestions {

    public static void main(String args[]){

        SLL ll = new SLL();

        ll.addToTail(10);

        ll.addToTail(20);

        ll.addToTail(30);

        ll.addToTail(40);

        ll.addToTail(50);

        ll.addToTail(40);

        ll.addToTail(50);

        ll.addToHead(11);

        ll.addToHead(12);

        ll.addToHead(13);

        ll.addToHead(14);

        ll.printList();

        ll.findMiddle();

        }

}

class Node{

        Node next;

        int val;

        public Node(){

                next = null;

        }

        public Node(int n){

                val = n;

                next = null;

        }

        

        public Node(Node ptr, int n){

                next = ptr;

                val = n;

        }

}

class SLL{

        Node head = null;

        Node tail = null;

        void addToHead(int n){

                head = new Node(head, n);

                if(tail == null){

                        tail = head;

                }

        }

        public void findMiddle() {

                Node tmp1 = head;

                Node tmp2 = head;

                int i = 0;

                for(;tmp1 != null; tmp1 = tmp1.next){

                        i ++;

                                if( i == 2){

                                        i = 0;

                                        tmp2 = tmp2.next;

                                }

               }

                System.out.println("Middle element is : "+tmp2.val);

        }

        void addToTail(int n){

                if(tail == null){

                        tail = new Node(n);

                }

                tail.next = new Node(n);

                tail = tail.next;

                if(head == null){

                        head = tail;

                }

        }

        

        void printList(){

                for(Node tmp = head; tmp != null; tmp = tmp.next){

                        System.out.print(tmp.val +" --> ");

                }

                System.out.println();

        }

}

Output:

14 --> 13 --> 12 --> 11 --> 10 --> 20 --> 30 --> 40 --> 50 --> 40 --> 50 --> 

Middle element is : 20

Find Max from two numbers without using if-else or comparison

/**
* Formula : Max = [(A+B)/2 ]   + [ |A -B| /2 ]
*
*/

private static int max(int i, int j) {

       int a = (i+j)/2;

       int b = Math.abs((i-j)/2);

       return a+b;

}

Union find problem:

Problem Statement: Suppose we have set of "n" nodes, if we want to connect them or if we want to check whether we have connection between these two nodes, then code below helps to find in the simplest way.
E.g.

/**
 * @author akash mahakode
 * @email akash.mahakode@gmail.com
 * http://issuesifaced.blogspot.in/
 *
 */
public class UnionFind {

int [] inputArr;
public static void main(String args[]){

UnionFind uf = new UnionFind(10);
boolean result = uf.isConnected(1,  9);
System.out.println("Are 1 and 9 connected? \nAns: "+ result);
uf.union(1, 9);
result = uf.isConnected(1,  9);
System.out.println("Are 1 and 9 connected? \nAns: "+ result);

result = uf.isConnected(1,  6);
System.out.println("Are 1 and 6 connected? \nAns: "+ result);
uf.union(1, 6);
result = uf.isConnected(1,  6);
System.out.println("Are 1 and 6 connected? \nAns: "+ result);


result = uf.isConnected(2,  6);
System.out.println("Are 2 and 6 connected? \nAns: "+ result);
uf.union(2, 6);
result = uf.isConnected(2,  6);
System.out.println("Are 1 and 6 connected? \nAns: "+ result);

result = uf.isConnected(2,  9);
System.out.println("Are 2 and 9 connected? \nAns: "+ result);

uf.print();
}

private void print() {
for (int i = 0; i < inputArr.length; i++) {
System.out.print(i+"  ");
}
System.out.println();
for (int i = 0; i < inputArr.length; i++) {
System.out.print(inputArr[i]+"  ");
}
}

/**
* Constructor which will initialize the input array to 0 to (size -1)
* e.g
*  0 1 2 3 4 5 6 7 8 9
* ---------------------
* |0|1|2|3|4|5|6|7|8|9|
* ---------------------
*
* @param size
*/
public UnionFind(int size){
inputArr = new int[size];
//initialize inputArr
System.out.println("Initial array:");
for (int i = 0; i < inputArr.length; i++) {
inputArr[i] = i;
System.out.print(inputArr[i]+"  ");
}
System.out.println();
}


/**
* @param a
* @param b
* @return true when a and b are connected directly or indirectly
*/
public boolean isConnected(int a, int b){
return (inputArr[a] == inputArr[b]);
}


/** connects a and b, that is it changes a to b in the array
* @param a
* @param b
*/
public void union(int a, int b){
int p = inputArr[a];
int q = inputArr[b];
for (int i = 0; i < inputArr.length; i++) {
if(inputArr[i] == p){
inputArr[i] = q;
}
}
}
}

Sorting Simplified: Insertion Sort

Hi All,

I am putting the code for insertion sort. You can either pass the numbers to be sorted via command-line or through GUI. Code is pasted below. Please mail me if you need further details...
+++++++++++++

package examples;

import javax.swing.JOptionPane;

/**

 * @author Akash Mahakode

 * @email akash.mahakode@gmail.com

 *

 */

public class InsertionSort {

//pseudocode

/*

 for j= 2 to A.length

{

      key = A[j]

      i = j-1

      while (i > 0 & A[i] > key)

     {

        A[i+1] = A[i]

        i = i-1

     }

     A[i+1] = key

}

*/

public static void main(String[] args) {

     int [] inputArray;

     if(args.length == 0){

          String str = JOptionPane.showInputDialog(null, "Please enter numbers to be sorted, \n seperate                               them by space");

          String array[] = str.split(" ");

          inputArray = new int[array.length];

          for (int i = 0; i < array.length; i++) {

          inputArray [i] = Integer.parseInt(array[i]);

          }

     }else{

               inputArray = new int[args.length];

               for (int i = 0; i < args.length; i++) {

               inputArray [i] = Integer.parseInt(args[i]);

     }

  }

insertionSort(inputArray);

}

private static void insertionSort(int[] inputArray) {

     System.out.println("Input Array is : ");

     String tempStrInput = "";

     String tempStrOutput = "";

     for (int i = 0; i < inputArray.length; i++) {

          System.out.print(inputArray[i]+ "  ");

          tempStrInput = tempStrInput + " " +inputArray[i];

     }

     //start : main algorithm implementation

     for(int j = 1; j < inputArray.length ; j ++){

          int key = inputArray[j];

          int i = j -1;

          while (i > -1 && inputArray[i] > key) {

               inputArray[i+1] = inputArray[i];

               i = i -1;

          }

     inputArray[i+1] = key;

}

//end : man algorithm implementation

     System.out.println();

     System.out.println("Sorted array is : ");

     for (int i = 0; i < inputArray.length; i++) {

          System.out.print(inputArray[i]+ "  ");

          tempStrOutput = tempStrOutput + " " +inputArray[i];

          }

JOptionPane.showMessageDialog(null, "Input : \n"+tempStrInput+"\n\n Output: \n "+tempStrOutput);

     }

}

++++++++++++