Find start of the loop in the linked list using Java...

Problem Statement:- Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION:-
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.

EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C

here is the code ...

       
public class Q5 {

 public static void main(String[] args) {

  Node head = new Node(1);    // head node of the linked list
  Node node1 = new Node(2);
  head.next = node1;
  Node node2 = new Node(3);
  node1.next = node2;
  Node node3 = new Node(4);
  node2.next = node3;
  Node node4 = new Node(5);
  node3.next = node4;
  Node node5 = new Node(6);
  node4.next = node5;
  Node node6 = new Node(7);
  node5.next = node6;
  node6.next = node3;        // here loop appears
  findNodeAtbeg(head);
 }

 public static void findNodeAtbeg(Node head) {
  Node slow = head;          //slow pointer
  Node fast = head;          //fast pointer

  while (fast != null) {
   slow = slow.next;
   fast = fast.next.next;
   if (slow == fast) {
    break;
   }
  }
  if (fast == null) {
   System.out.print("There is no loop exit");
  }
  slow = head;
  while (slow != fast) {
   slow = slow.next;
   fast = fast.next;
  }
  System.out.println("Node where loop begins contains data item as - "
    + fast.data);
 }
}

class Node {
 int data;
 Node next;

 Node(int d) {
  data = d;
  next = null;
 }
}

       
 

Producer Consumer multithreading problem using Java....

Here is the code .....

       

public class ProducerConsumerProblem {

 public static void main(String[] args) {
        
  DataClass c=new DataClass();
  Producer p1 = new Producer(c, 1);
  Consumer c1 = new Consumer(c, 1);
  p1.start();
  c1.start();

 }
}

class DataClass {
 int data;
 boolean dataAvailable = false;

 public synchronized int get() throws InterruptedException {

  while (dataAvailable == false) {
   wait();
  }
  dataAvailable = false;
  notifyAll();
  return data;
 }

 public synchronized void setData(int content) throws InterruptedException {

  while (dataAvailable == true) {
   wait();
  }
  data = content;
  dataAvailable = true;
  notifyAll();
 }
}

class Producer extends Thread {
 private DataClass dataObject;
 private int number;

 public Producer(DataClass dataClassReference, int num) {
  dataObject = dataClassReference;
  number = num;
 }

 public void run() {
  for (int i = 0; i < 10; i++) {
   try {
    dataObject.setData(i);
   } catch (InterruptedException e1) {
    // TODO Auto-generated catch block
    e1.printStackTrace();
   }
   System.out.println("Producer #" + this.number + " put: " + i);
   try {
    sleep((int) (Math.random() * 100));
   } catch (InterruptedException e) {
   }
  }
 }
}

class Consumer extends Thread {
 private DataClass dataObject;
 private int number;

 public Consumer(DataClass dataClassReference, int num) {
  dataObject = dataClassReference;
  number = num;
 }

 public void run() {
  int value = 0;
  for (int i = 0; i < 10; i++) {
   try {
    value = dataObject.get();
   } catch (InterruptedException e) {
    // TODO Auto-generated catch block
    e.printStackTrace();
   }
   System.out.println("Consumer #" + this.number + " got: " + value);
  }
 }
}

       
 

Check whether a string is a rotation of another string using Java .....

here is the code....

Problem - "ravgau" is a rotation of "gaurav".

       

public class Demo {

 public static void main(String[] args) {

  String s1 = "gaurav";
  String s2 = "avgaur";

  if (isSubString(s1 + s1, s2))
   System.out.print("String :" + s2 + " is a rotation of string :" + s1);
  else
   System.out.print("String :" + s2 + " is not a rotation of string :" + s1);

 }

 public static boolean isSubString(String s1, String s2) {
  int k = 0;
  int i = 0;
  int t;
  if (s1.length() < s2.length()) {
   return false;
  } else {
   while (i < (s1.length() - s2.length() + 1)) {
    if (s1.charAt(i) == s2.charAt(k)) {
     t = i;
     t++;
     k++;
     // Always make sure that conditions in loop should appear in
     // correct order otherwise it could give an exception
     while ((k < s2.length()) && (s1.charAt(t) == s2.charAt(k))) {
      t++;
      k++;
     }
     if (k == s2.length())
      return true;
     else
      k = 0;
    }
    i++;
   }
  }
  return false;
 }
}

       
 

Remove duplicates from a string without using any additional data structure using Java....

here is the code .....

       

public class Demo {

 public static void main(String[] args) {
  String name = "GAURAV KUMAR YADAV1111";
  dupliactesRemoved(name);
 }

 //This method assumes that string is made up of only small letter characters i. "a....z"
 public static void dupliactesRemoved(String temp) {

  int vector = 0;
  int val;
  System.out.println("Given string after removing duplicates characters is below :");
  for (int i = 0; i < temp.length(); i++) {
   val = temp.charAt(i) - 'a';
   if ((vector & (1 << val)) == 0) {
    System.out.print(temp.charAt(i));
    vector = vector | (1 << val);
   }
  }
 }
}

       
 

Determine if a string has all unique characters without using any additional data structure using Java....

Here is the the code ....

       
public class Demo {

 public static void main(String[] args) {

  String name = "gaurv1";
  if (isUniqueCharString(name))
   System.out.print("String is made up of unique chars");
  else
   System.out.print("String is not made up of unique chars");

 }

 //here we are using an integer as a bit vector....
 public static boolean isUniqueCharString(String temp) {
  int vector = 0;
  int val;
  for (int i = 0; i < temp.length(); i++) {
   val = temp.charAt(i) - 'a';
   if ((vector & (1 << val)) > 0)
    return false;
   vector = vector | (1 << val);
  }
  return true;
 }

 // Alternate solution - we can sort the characters of string and then
 // compare the neighbors
}

       
 

Find k closest elements in a sorted array using Java ......

here is the code .....


/*Given a sorted array arr[] and a value X, find the k closest elements to X in arr[].
 Examples:

 Input: K = 4, X = 35
 arr[] = {12, 16, 22, 30, 35, 39, 42,
 45, 48, 50, 53, 55, 56}
 Output: 30 39 42 45
 Note that if the element is present in array, then it should not be in output, only the other closest elements are required.
 */

       

public class FindKClosestElements {

 public static void main(String args[]) {

  int[] arr = {
   12,
   16,
   22,
   30,
   35,
   39,
   42,
   45,
   48,
   50,
   53,
   55,
   56
  };
  int element = 100;
  int k = 5;
  int m;
  int n;
  int distance1;
  int distance2;

  // case if element is is larger than even the last element in the array
  if (arr[arr.length - 1] < element) {
   n = arr.length - 1;
   while (k != 0) {
    System.out.print(arr[n]);
    System.out.print(" ");
    k--;
    n--;
   }
   return;
  }

  for (int i = 0; i < arr.length; i++) {
   if (arr[i] >= element) {
    m = i - 1;
    if (arr[i] == element)
     n = i + 1;
    else
     n = i;
    while (m >= 0 && n < arr.length && k != 0) {

     distance1 = arr[n] - element;
     distance2 = element - arr[m];

     if (distance1 <= distance2) {
      System.out.print(arr[n]);
      System.out.print(" ");
      k--;
      n++;
     } else {
      System.out.print(arr[m]);
      System.out.print(" ");
      k--;
      m--;
     }
    }
    if (k != 0) {
     if (m > 0)
      while (k != 0) {
       System.out.print(arr[m]);
       System.out.print(" ");
       m--;
       k--;
      } else
      while (k != 0) {
       System.out.print(arr[n]);
       System.out.print(" ");
       k--;
       n++;
      }
    }
    if (k == 0)
     return;
    else
     continue;
   }
  }
 }


}

       
 

Merging two sorted arrays using Java ....

here is the code .....

       
public class MergingSortedLists {

 public static void main(String args[]) {

  int[] arr1 = {
   1,
   4,
   5,
   43,
   56,
   59
  };
  int[] arr2 = {
   2,
   3,
   6,
   34,
   36,
   42,
   67
  };
  int[] sortedList = new int[arr1.length + arr2.length];
  mergeLists(arr1, arr2, sortedList);
 }

 public static void mergeLists(int[] arr1, int[] arr2, int[] sortedList) {
  int k = 0;
  int j = 0;
  int t = 0;
  while (k < arr1.length && j < arr2.length) {
   if (arr1[k] <= arr2[j]) {
    sortedList[t] = arr1[k];
    t++;
    k++;
   } else {
    sortedList[t] = arr2[j];
    t++;
    j++;
   }
  }
  if (k != arr1.length) { //case where arr1 is left with elements not added to sorted list
   while (k < arr1.length) {
    sortedList[t] = arr1[k];
    t++;
    k++;
   }
  }
  if (j != arr2.length) { //case where arr2 is left with elements not added to sorted list
   while (j < arr2.length) {
    sortedList[t] = arr2[j];
    t++;
    j++;
   }
  }
  for (int s: sortedList) {
   System.out.print(s);
   System.out.print(" ");

  }
 }
}

       
 

Check whether two numbers are of opposite signs or not using Java .....

Problem -Two numbers are given ,you have to evaluate whether they are of opposite signs or not

Logic -Numbers are represented in 2's complemented form in computer where sign bit 0 means it is 

            positive number and 1 means it is negative .

here is the code ......

       
public class CheckOppositeSigns {

 public static void main(String args[]) {
  int x = 2;
  int y = -13;
  if (checkForOppositeSigns(x, y))
   System.out.print("Yes both the integers are of opposite signs");
  else
   System.out.print("Both the integers are of same sign");
 }

 public static boolean checkForOppositeSigns(int x, int y) {

  int signofFirstVariable = (x >> 31) ^ (0x1); //shifting the variable to place the sign bit at unit                                                                                     //position and then XOR with 000000000
  int signofSecondVariable = (y >> 31) ^ (0x1);
  if (signofFirstVariable != signofSecondVariable)
   return true;

  return false;
 }
}

       
 

Binary Search Tree implemented using Java ....

Binary Search Tree -

A binary search tree is a rooted binary tree, whose internal nodes each store a key (and optionally, an associated value) and each have two distinguished sub-trees, commonly denoted left and right. The tree additionally satisfies the binary search tree property, which states that the key in each node must be greater than all keys stored in the left sub-tree, and smaller than all keys in right sub-tree.^[1]:287 (The leaves (final nodes) of the tree contain no key and have no structure to distinguish them from one another. Leaves are commonly represented by a special leaf or nil symbol, a NULL pointer, etc.)

here is the code ....

       
public class BinarySearchTreeImplementation {

 public static void main(String args[]) {

  BinarySearchTree tree = new BinarySearchTree();
  tree.addNode(50);
  tree.addNode(10);
  tree.addNode(100);
  tree.addNode(20);
  tree.addNode(200);
  tree.addNode(99);
  System.out.println("Binary Search Tree after the insertion of the nodes");
  tree.printBSTPreOrder();
 }

}

class BinarySearchTree {

 Node root;

 class Node {
  int data;
  Node leftChild;
  Node rightChild;

  Node(int d) {
   data = d;
   leftChild = null;
   rightChild = null;
  }
 }

 public void addNode(int d) {
  Node new_node = new Node(d);
  Node temp;
  if (root != null) {
   temp = root;
   Node parent_node = findPositionForNodeToAdd(temp, d);
   if (parent_node.data < d)
    parent_node.rightChild = new_node;
   else
    parent_node.leftChild = new_node;

  } else {
   root = new_node;
  }
 }

 public Node findPositionForNodeToAdd(Node root, int d) {

  if (root.leftChild == null && root.rightChild == null)
   return root;
  else if (root.data >= d) {
   if (root.leftChild != null)
    return findPositionForNodeToAdd(root.leftChild, d);
   else
    return root;
  } else if (root.data < d) {
   if (root.rightChild != null)
    return findPositionForNodeToAdd(root.rightChild, d);
   else
    return root;
  }

  return null;
 }

 //Prints the binary search tree in pre order traversal
 public void printBSTPreOrder() {
  if (root == null)
   System.out.println("Binary Search Tree is empty till now");
  else {
   Node temp = root;
   preOrder(temp);
  }
 }

 private void preOrder(Node root) {
  if (root == null)
   return;
  else {
   System.out.print(root.data + " ");
   preOrder(root.leftChild);
   preOrder(root.rightChild);
  }
 }
}

       
 

Sorting a Linked List contains only 0's,1's and 2's using Java ...

Problem - Given an unsorted Linked List containing values from the set {0,1,2}                       only sort it using java. 

Here is the code ....

       

public class SortLinkedList {

 public static void main(String[] args) {

  LinkedList list = new LinkedList();
  list.push(0);
  list.push(1);
  list.push(0);
  list.push(1);
  list.push(2);
  list.push(2);
  list.push(0);
  list.push(1);
  list.push(1);
  list.push(2);
  list.push(0);

  System.out.println("Before sorting");
  list.printList();
  System.out.println();
  list.sortList();
  System.out.println("After sorting");
  list.printList();
 }

}
class LinkedList {

 private Node head;

 class Node {
  int data;
  Node next;
  Node(int d) {
   next = null;
   data = d;
  }
 }

 public void push(int d) {

  Node new_Node = new Node(d);

  new_Node.next = head;
  head = new_Node; //Adding elements at the start of linked list
 }

 public void printList() {
  Node temp = head;
  while (temp != null) {
   System.out.print(temp.data);
   temp = temp.next;
   System.out.print(" ");
  }
 }
 public void sortList() {
  int[] count = new int[3];
  count[0] = 0;
  count[1] = 0;
  count[2] = 0;
  Node temp = head;
  while (temp != null) {
   if (temp.data == 0)
    count[0]++;
   else if (temp.data == 1)
    count[1]++;
   else count[2]++;
   temp = temp.next;
  }
  temp = head;
  int i = 0;
  while (temp != null) {
   if (count[i] == 0)
    i++;
   else {
    temp.data = i;
    temp = temp.next;
    count[i]--;
   }
  }
 }
}

       
 

Sort anagram strings using Java....

Problem Statement - Given a list of strings ,sort the list in such a fashion that anagrams are always                                       adjacent to each other.

here is the code ........

       
import java.io.*;
import java.util.*;

class sortanagram {

 public static boolean anagram(String arg1, String arg2) {
  int f;
  int[] arr = new int[256];
  if (arg1.length() == arg2.length()) {
   for (int i = 0; i < arg1.length(); i++) {
    f = arg1.charAt(i);
    arr[f] = arr[f] + 1;
   }

   for (int k = 0; k < arg2.length(); k++) {
    f = arg2.charAt(k);
    arr[f] = arr[f] - 1;
   }
   for (int d = 0; d < 256; d++) {
    if (arr[d] != 0) {
     return false;
    }

   }
   return true;
  } else {
   return false;
  }

 }

 public static void main(String args[]) {

  String[] args3 = {
   "abcd",
   "save",
   "dcba",
   "dog",
   "easv",
   "god",
   "free"
  };
  String temp;
  int p;

  for (int i = 0; i < args3.length; i++) {
   p = i;
   for (int l = i + 1; l < args3.length; l++) {
    if (anagram(args3[i], args3[l]) == true) {


     p++;
     temp = args3[l];
     args3[l] = args3[p];
     args3[p] = temp;

    }

   }

  }

  for (int r = 0; r < args3.length; r++)
   System.out.println(args3[r]);

 }

}

       
 

Prime number generator using Java....

Input Format- First line of input is number of test cases    //No. of Inputs

                        Second line contains two numbers separated by space ,all prime numbers generated                             will lie between them.
               
      e.g-            2                                //No. of Test cases
                        10 100                       //First test case
                        101 200                     //Second Case

here is the code ....

       
import java.io.*;
import java.util.*;
import java.lang.Math.*;

public class PrimeNumberGenerator {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);

  int[] primes = new int[4000];
  int numprimes = 0;

  primes[numprimes++] = 2;
  for (int i = 3; i <= 32000; i += 2) {
   boolean isprime = true;
   double cap = Math.sqrt(i) + 1.0;

   for (int j = 0; j < numprimes; j++) {
    if (j >= cap) break;
    if (i % primes[j] == 0) {
     isprime = false;
     break;
    }
   }
   if (isprime) primes[numprimes++] = i;
  }


  int T, N, M;

  T = in .nextInt();

  for (int t = 0; t < T; t++) {
   if (t > 0) System.out.println("");

   M = in .nextInt();
   N = in .nextInt();

   if (M < 2) M = 2;

   boolean[] isprime = new boolean[100001];
   for (int j = 0; j < 100001; j++) {
    isprime[j] = true;
   }

   for (int i = 0; i < numprimes; i++) {
    int p = primes[i];
    int start;

    if (p >= M) start = p * 2;
    else start = M + ((p - M % p) % p);

    for (int j = start; j <= N; j += p) {
     isprime[j - M] = false;
    }
   }

   for (int i = M; i <= N; i++) {
    if (isprime[i - M]) System.out.println(i);
   }
  }
 }
}

       
 

Optimized Bubble Sort using Java .....

Quick Logic - In bubble sort we are compairing adjacent elements, swap them if we need to and this                          will continue upto (N-1) passes .So optimized bubble sort will be most efficient if the                          array is already sorted or almost sorted.

Optimization Logic - We are checking that if two continues passes of the bubble sort are same then                            we don't have to continue further because array has already become sorted till now.

here is the code....

       
public class OptimizedBubbleSort {

 static int[] arr = {
  1,
  2,
  3,
  4,
  5,
  6,
  70,
  18,
  9
 };
 static boolean[] swapFlag = new boolean[arr.length - 1]; //to keep track that in each pass swap happens or not
 static int temp;

 public static void main(String[] args) {

  bubbleSort();
  for (int i = 0; i < arr.length; i++) {
   System.out.print(arr[i] + " ");
  }
 }

 public static void bubbleSort() {

  for (int i = 0; i < arr.length - 1; i++) {
   for (int y = 0; y < arr.length - i - 1; y++) {
    if (arr[y] > arr[y + 1]) {
     swap(y, y + 1);
     swapFlag[i] = true;
    }
   }
   System.out.println(i + " pass");
   if (i != 0) {
    if (swapFlag[i] == false && swapFlag[i - 1] == false) //condition where we are checking that int two succesive passes
     return;
   }
  }
 }

 public static void swap(int k, int r) {
  temp = arr[r];
  arr[r] = arr[k];
  arr[k] = temp;
 }

}

       
 

Dijkstra's Algorithm using Min Heap to find shortest path from source to all other nodes in Java .....

here is the code .....

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

public class DijkstraProblem {

 static int[][] costMatrix;
 static String line;
 static String[] lineValues;
 static int totalNodes;
 static int source;
 static int[] heapHolder; //to hold the cost of path to nodes 
 static int[] nodeNameHolder; //to hold the nodes corresponding to the heap cost in heapholder
 static int heapLength;
 static int smallest;
 static int left; // left child index
 static int right; // right child index
 static int temp;
 static int reducedNode = 0;
 static int reducedNodePathCost = 1;
 static int[] deletedNode; //to hold the cost and the node number everytime we delete root node from heap 
 static int newCostViaReducedNode;


 public static void main(String[] args) throws IOException {

  String path = "C:/Users/gauravy/Desktop/matrix.txt";
  loadfile(path);
  BufferedReader gr = new BufferedReader(new InputStreamReader(System.in));
  System.out.println("Please enter the node number from where you want shortest path to all nodes ...");
  source = Integer.parseInt(gr.readLine());
  applyDijkstra(source);

  System.out.println("Shortest path from source to all other nodes is below sequentially.....");
  for (int v = 0; v < totalNodes; v++) {
   System.out.print("source to node " + v + " cost is - " + costMatrix[source][v]);
   System.out.println("");
  }


 }

 // method to load the adjacency matrix for graph from the text file
 public static void loadfile(String path) throws IOException {

  FileReader fr = new FileReader(new File(path));
  BufferedReader br = new BufferedReader(fr);

  line = br.readLine();
  lineValues = line.split(" ");
  totalNodes = lineValues.length;
  costMatrix = new int[totalNodes][totalNodes];
  heapHolder = new int[totalNodes];
  deletedNode = new int[2];
  //viaNodeHolder = new int[totalNodes];
  nodeNameHolder = new int[totalNodes];
  heapLength = lineValues.length;

  int r = 0;

  while (line != null) {
   for (int c = 0; c < totalNodes; c++) {
    costMatrix[r][c] = Integer.parseInt(lineValues[c]);

   }
   r++;
   line = br.readLine();
   if (line != null)
    lineValues = line.split(" ");
  }
  fr.close();
  br.close();
 }

 // here we are applying the Dijkstra's algorithm
 public static void applyDijkstra(int source) {

  //viaNodeHolder[0] = 0;
  //nodeNameHolder[0]=0;
  for (int y = 0; y < heapLength; y++) {
   heapHolder[y] = Integer.MAX_VALUE;
   //viaNodeHolder[y] = 0;
   nodeNameHolder[y] = y;
  }
  heapHolder[source] = 0;

  buildMinHeap();

  for (int k = 0; k < totalNodes; k++) {
   deleteRoot();

   for (int p = 0; p < heapLength; p++) {
    newCostViaReducedNode = deletedNode[reducedNodePathCost] + costMatrix[deletedNode[reducedNode]][nodeNameHolder[p]];

    if (newCostViaReducedNode < heapHolder[p]) {
     heapHolder[p] = newCostViaReducedNode;
     costMatrix[source][nodeNameHolder[p]] = newCostViaReducedNode;
    }
    min_Heapify(0);
   }
  }
 }

 public static void buildMinHeap() {
  for (int p = heapHolder.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }

 // min heapify algorithm implemented here
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heapLength) && (heapHolder[left] < heapHolder[p]))
   smallest = left;
  else
   smallest = p;

  if ((right < heapLength) && (heapHolder[right] < heapHolder[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }

 // returns index of left child
 public static int leftChild(int k) {
  return (2 * k + 1);
 }

 // returns of right child
 public static int rightChild(int i) {
  return (2 * i + 2);
 }

 // for swapping purpose
 public static void swap(int a, int b) {

  temp = heapHolder[a];
  heapHolder[a] = heapHolder[b];
  heapHolder[b] = temp;

  temp = nodeNameHolder[a];
  nodeNameHolder[a] = nodeNameHolder[b];
  nodeNameHolder[b] = temp;
 }

 // for deletion of root node from heap
 public static void deleteRoot() {

  deletedNode[reducedNode] = nodeNameHolder[0];
  deletedNode[reducedNodePathCost] = heapHolder[0];

  heapHolder[0] = heapHolder[heapLength - 1];
  //viaNodeHolder[0] = viaNodeHolder[heapLength - 1];
  nodeNameHolder[0] = nodeNameHolder[heapLength - 1];

  heapLength--;
  min_Heapify(0);
 }

}

       
 

Max Heap using Java.....

here is the code...

       
public class BuildMaxHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int largest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMaxHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMaxHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   max_Heapify(p);
  }
 }
 public static void max_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] > heap[p]))
   largest = left;
  else largest = p;

  if ((right < heap.length) && (heap[right] > heap[largest]))
   largest = right;

  if (largest != p) {
   swap(largest, p);
   max_Heapify(largest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}

       
 

Min Heap using Java.....

here is the code....

       

public class BuildMinHeapProblem {
 static int[] heap = {
  80,
  90,
  32,
  1,
  40,
  50,
  45,
  22,
  12,
  23,
  33
 };
 static int smallest;
 static int left; //left child index
 static int right; //right child index
 static int temp;

 public static void main(String[] args) {
  buildMinHeap();
  for (int k: heap) {
   System.out.print(k);
   System.out.print(" ");
  }
 }
 public static void buildMinHeap() {
  for (int p = heap.length / 2 - 1; p >= 0; p--) {
   min_Heapify(p);
  }
 }
 public static void min_Heapify(int p) {
  left = leftChild(p);
  right = rightChild(p);

  if ((left < heap.length) && (heap[left] < heap[p]))
   smallest = left;
  else smallest = p;

  if ((right < heap.length) && (heap[right] < heap[smallest]))
   smallest = right;

  if (smallest != p) {
   swap(smallest, p);
   min_Heapify(smallest);
  }
 }
 public static int leftChild(int k) {
  return (2 * k + 1);
 }
 public static int rightChild(int i) {
  return (2 * i + 2);
 }
 public static void swap(int a, int b) {
  temp = heap[a];
  heap[a] = heap[b];
  heap[b] = temp;
 }

}
       
 

Find all missing numbers in a sequence......

Problem:- Given a list of numbers from 1 to N where more than one numbers are                    missing between 1 to N find all of them .

here is the code ......

       
public class AllMissingNumbersProblem {
 static int missNum;
 static int largestNum;
 static boolean[] keepTrack;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11
  };
  largestNum = findLargestNumber(arr);
  keepTrack = new boolean[largestNum + 1];

  for (int i = 0; i < arr.length; i++)
   keepTrack[arr[i]] = true;

  System.out.println("Missing numbers are listed below....");
  for (int p = 1; p < keepTrack.length; p++) {
   if (!keepTrack[p])
    System.out.println(p);
  }

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}

       
 

Find the missing number......

Problem:- Given a list of number from 1 to N find the missing number ....

Logic -Just calculate sum of N natural numbers (n*(n+1))/2.
            Then subtract the sum of all given numbers from above calculated sum                    and you will get missing number.

here is the code......

       

public class MissingNumberProblem {
 static int missNum;
 static int largestNum;
 static int naturalSum;
 static int totalNumbersSum;
 public static void main(String args[]) {

  int[] arr = {
   4,
   2,
   6,
   5,
   3,
   1,
   8,
   12,
   9,
   11,
   7
  };
  largestNum = findLargestNumber(arr);
  naturalSum = (largestNum * (largestNum + 1)) / 2;

  for (int i = 0; i < arr.length; i++) {
   totalNumbersSum = totalNumbersSum + arr[i];
  }

  missNum = naturalSum - totalNumbersSum;
  System.out.println("Missing number is " + missNum);

 }
 public static int findLargestNumber(int[] arr) {
  int temp;
  for (int i = 0; i < arr.length - 1; i++) {
   if (arr[i] > arr[i + 1]) {
    temp = arr[i + 1];
    arr[i + 1] = arr[i];
    arr[i] = temp;
   }
  }
  return arr[arr.length - 1];
 }
}