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];
 }
}
       
 

Tic-Tac-Toe Game using Java.......

Features - 1.This program always takes constant time for playing a move and       evaluating winning condition.

2.Game can be played on board of any size ,currently I've configured it for max Board size of 10 .

3.Currently only multiplayer mode is implemented ,single player with bot will be implemented soon .

NOTE-  Conventions to play Tic-Tac-Toe game are as follows...
1.When it asked for size of the board enter single digit number for e.g -if you want to play on 3*3 then just enter "3" (without quotes of course) and press "enter".
         
 2.When you want to play a move enter the row and column index of the position separated by a space .
 e.g - If you want to enter a move on first column of first row then just                     enter "1 1" ( without double quotes ) and then press "enter".  

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

       

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.*;

public class TicTacToeProblem {
 static int size;
 static int mode;
 static HashMap < String, ArrayList < String >> player1RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 1 
 static HashMap < String, ArrayList < String >> player2RowsAndDiagonals = new HashMap < String, ArrayList < String >> (); //to keep track of rows and diagonal formation for player 2
 static HashMap < String, ArrayList < String >> player1Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 1 
 static HashMap < String, ArrayList < String >> player2Columns = new HashMap < String, ArrayList < String >> (); //to keep track of column formation for player 2 
 static HashSet < String > filledPositions = new HashSet < String > ();

 public static void main(String[] args) throws NumberFormatException,
  IOException {
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   System.out.println("Please enter the size of board in numeral");
   size = Integer.parseInt(br.readLine());

   while ((size > 10) == true) {
    System.out.println("Max size allowed is 10");
    System.out.println("please re enter the size");
    size = Integer.parseInt(br.readLine());
   }
   System.out.println("please enter playing mode number");
   System.out.println("1.two player");
   System.out.println("2.with bot");
   mode = Integer.parseInt(br.readLine());
   while (mode != 1 && mode != 2) {
    System.out.println("Please enter appropriate choice of mode 1 or 2");
    mode = Integer.parseInt(br.readLine());
   }
   if (mode == 1) {
    System.out.println("Initializing Setup..........");
    multiplayer(size);
   } else
    withBot(size);
   br.close();
  }

 public static void multiplayer(int size) throws IOException {
  String[] playerMove = null;
  String move = null;
  int coordinateX;
  int coordinateY;
  int player;
  int secondDiagonalSum = size + 1;
  int maxMoves = size * size;

  for (int i = 1; i <= size; i++) { //here just initializing arrayLists for each rows and each columns for both players
   ArrayList < String > rowList1 = new ArrayList < String > ();
   ArrayList < String > rowList2 = new ArrayList < String > ();
   ArrayList < String > columnList1 = new ArrayList < String > ();
   ArrayList < String > columnList2 = new ArrayList < String > ();
   player1RowsAndDiagonals.put((new Integer(i).toString()), rowList1);
   player2RowsAndDiagonals.put((new Integer(i).toString()), rowList2);
   player1Columns.put((new Integer(i).toString()), columnList1);
   player2Columns.put((new Integer(i).toString()), columnList2);
  }

  ArrayList < String > player1diag1 = new ArrayList < String > (); //here initializing arrayLists to keep track of both the diagonals for both players
  ArrayList < String > player1diag2 = new ArrayList < String > ();
  ArrayList < String > player2diag1 = new ArrayList < String > ();
  ArrayList < String > player2diag2 = new ArrayList < String > ();

  player1RowsAndDiagonals.put("diag1", player1diag1);
  player1RowsAndDiagonals.put("diag2", player1diag2);
  player2RowsAndDiagonals.put("diag1", player2diag1);
  player2RowsAndDiagonals.put("diag2", player2diag2);

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  System.out.println("OK,now start playing enter your choices alternatively");

  for (int i = 0; i < maxMoves; i++) {
   if (i % 2 == 0) {
    System.out.println("player 1 turn");
    player = 1;
   } else {
    System.out.println("player 2 turn");
    player = 2;
   }
   move = br.readLine();
   while (filledPositions.contains(move) == true) { //check for already played Move
    System.out.println("this move has been already played please enter another move");
    move = br.readLine();
   }
   filledPositions.add(move);
   playerMove = move.split(" ");
   coordinateX = Integer.parseInt(playerMove[0]);
   coordinateY = Integer.parseInt(playerMove[1]);

   switch (player) {
    case 1:
     if (playerMove[0].equals(playerMove[1])) { //condition for one of the position in diagonal one
      player1RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum) //condition for one of the position in diagonal two 
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player1RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player1Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player1RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player1Columns.get(playerMove[1]).size() == size) || (player1RowsAndDiagonals.get("diag1").size() == size) || (player1RowsAndDiagonals.get(playerMove[0]).size() == size) || (player1RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     }
     break;
    case 2:
     if (playerMove[0].equals(playerMove[1])) {
      player2RowsAndDiagonals.get("diag1").add(playerMove[1]);
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 1 wins game is finished");
       return;
      }
     } else {
      player2RowsAndDiagonals.get(playerMove[0]).add(playerMove[1]);
      player2Columns.get(playerMove[1]).add(playerMove[0]);

      if ((coordinateX + coordinateY) == secondDiagonalSum)
       player2RowsAndDiagonals.get("diag2").add(playerMove[1]);

      if ((player2Columns.get(playerMove[1]).size() == size) || (player2RowsAndDiagonals.get("diag1").size() == size) || (player2RowsAndDiagonals.get(playerMove[0]).size() == size) || (player2RowsAndDiagonals.get("diag2").size() == size)) {
       System.out.println("Player 2 wins game is finished");
       return;
      }
     }
     break;
    default:
     break;
   }
  } //end of loop 
  System.out.println("Match Tie NO one Wins");
 }



 public static void withBot(int size) {
  System.out.println("Working on it, this mode will be added soon till then keep playing multiplayer mode");
  return;
 }
}

       
 

Java Program to find Minimum steps to make an integer from two variables by repeatedly adding them ......

Problem Statement- Harsh just loves numbers and loves to have fun with them . Apparently he has two numbers with him , say X and Y . Both of them are integers . Now from these numbers he wants another number , say L . But he doesn’t know how to derive it and needs your help . Given the two numbers you can add one to another , and you can do this any number of times . For example, you can add X to Y , or Y to X , and this can be done until any combination makes either X equal toL or Y equal to L .

“Well , this might actually lead to a solution”, said Harsh, ”but can you do it in a minimum number of operations ?”.

Just to make this problem a little simple let’s assume both the values of X and Y is 1 .

Input Format:

The first line contains T, the number of test cases. For each test case, the first line contains L ,the value that Harsh wants .

Output Format:

For each test case, output the required minimum number of operations .

Problem Link- ( https://www.hackerearth.com/problem/algorithm/simple-addition )

here is the code ....

       
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class TestClass {
 static int evaluateStrings(int a, int b) {
  if (b == 0 && a != 1) return 100000000;
  if (b == 0 && a == 1) return -1;
  else return (a / b + evaluateStrings(b, a % b));
 }

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

  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  String line = br.readLine();
  int N = Integer.parseInt(line);
  for (int i = 1; i <= N; i++) {

   int x = Integer.parseInt(br.readLine());
   int ans = 100000000;
   for (int j = 1; j <= x; j++) {
    int tmp = evaluateStrings(x, j);

    if (tmp < ans) ans = tmp;
   }
   System.out.println(ans);
  }


 }
}