Category Archives: Mathematics

Recursively Finding Greatest Common Divisor (GCD) – Java Implementation

By | |
Leave a comment

This articles shows a java program that finds a greatest common divisor between two input integers and also prints the intermediate steps of recursion. Can you think about the complexity of this algorithm? It is O(Log(N)) where N is the largest number of the two. See the analysis here.

package com.icodejava.research.ready;
/**
 * 
 * @author Kushal Paudyal
 * Created on: 2/8/2017
 * Last Modified on: 2/8/2017
 * 
 * Recursive way of finding the GCD (Greatest Common Divisor)
 */
public class GCDRecursive {
	
	 public static int gcd(int a, int b) {
		 System.out.println("First Number: " + a + " Second Number: " + b);
	        if (a < 0 || b < 0) {
	            throw new IllegalArgumentException("No GCD of negative integers");
	        }
	        return b == 0 ? a : gcd(b, a % b);
	    }
	 
	 public static void main(String args []) {
		 System.out.println("Greatest Common Divisor of 35 and 21 is " + gcd(35,21));
	 }

}

The following is the output of this program.

First Number: 35 Second Number: 21
First Number: 21 Second Number: 14
First Number: 14 Second Number: 7
First Number: 7 Second Number: 0
Greatest Common Divisor of 35 and 21 is 7

In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation

By | | , ,
Leave a comment

Below, you will find a java implementation of class that does a matrix or 2 dimensional array rotation both clockwise and anti clockwise. The approach used here does not take extra buffer i.e. does the stuff IN-PLACE. There is another article in this blog where I have implemented this using extra buffer space.

package com.icodejava.blog.published.maths;

import java.util.Arrays;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how to rotate a NxN array 90 degrees using no extra buffer.
   e.g. 
     [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
	 
	 should appear as
	 
	 [[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
	 for a 90 degrees counter clockwise rotation

	 
	 [[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]
	 for a 90 degrees clockwise rotation
	 
 */

public class Rotate2DArrayInPlace {
		
public static void main (String args [] ) throws Exception {
		
		Integer [] [] myNxNArray = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myNxNArray));
		Integer [][] rotatedInPlace = rotateMatrixInPlaceCounterClockwise(myNxNArray);
		
		System.out.println("ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlace));
		
		//The array referenced in above definition myNxNArray is changed so you will need to redefine
		Integer [] [] myNxNArray1 = new Integer [][] {
			{1, 2, 3, 4, 5},
			{6, 7, 8, 9, 10},
			{11, 12, 13, 14, 15},
			{16,17,18,19,20},
			{21,22,23,24,25}
		};
		
		Integer [][] rotatedInPlaceClockwise = rotateMatrixInPlaceClockwise(myNxNArray1);
		
		System.out.println("ROTATED IN PLACE - 90 degrees CLOCKWISE");
		System.out.println(Arrays.deepToString(rotatedInPlaceClockwise));
		
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceCounterClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

		int n = matrix[0].length;
		int tmp;
		for (int i = 0; i < n / 2; i++) {
			for (int j = i; j < n - i - 1; j++) {
				tmp = matrix[i][j];
				matrix[i][j] = matrix[j][n - i - 1];
				matrix[j][n - i - 1] = matrix[n - i - 1][n - j - 1];
				matrix[n - i - 1][n - j - 1] = matrix[n - j - 1][i];
				matrix[n - j - 1][i] = tmp;
			}

		}
		return matrix;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
	 */
	public static Integer[][] rotateMatrixInPlaceClockwise(Integer[][] matrix) throws Exception {
		
		if(matrix.length == 0 || matrix.length != matrix[0].length) {
			throw new Exception ("Invalid Input");
		}

		int n = matrix.length;
		int top;
		for (int i = 0; i < n / 2; i++) {
			
			for (int j = i; j < n - i - 1; j++) {
				
				top = matrix[i][j];
				matrix[i][j] = matrix[n - j - 1][i];
				matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
				matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
				matrix[j] [n - i - 1] = top;
			
			}

		}
		return matrix;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE
[[5, 10, 15, 20, 25], [4, 9, 14, 19, 24], [3, 8, 13, 18, 23], [2, 7, 12, 17, 22], [1, 6, 11, 16, 21]]
ROTATED IN PLACE - 90 degrees CLOCKWISE
[[21, 16, 11, 6, 1], [22, 17, 12, 7, 2], [23, 18, 13, 8, 3], [24, 19, 14, 9, 4], [25, 20, 15, 10, 5]]

Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation

By | | , ,
Leave a comment

Below, you will find a java implementation of class that does a matrix or 2 dimensional array rotation both clockwise and anti clockwise. The approach used here takes extra buffer. There is another article in this blog where I have implemented this in place i.e. without requiring extra buffer space.

package com.icodejava.blog.published.maths;

import java.util.Arrays;

/**
 * 
 * @author Kushal Paudyal 
 * Created on: 01/05/2017 
 * Last Modified on: 01/05/2017
 *
 * This class demonstrates how to rotate a mxn array 90 degrees using extra buffer
   e.g. 
     1  2  3 4 5
	 6  7  8 9 10
	 11 12 13 14 15
	 
	 should appear as
	 
	 11 6 1
	 12 7 2
	 13 8 3
	 14 9 4
	 15 10 5
	 
	 for a 90 degrees clockwise rotation
	 
	 and 
	 
	 5 10 15
	 4 9 14
	 3 8 13
	 2 7 12
	 1 6 11
	 
	 for a 90 degrees counterclockwise rotation
 */
public class Rotate2DArray {

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

		// define two dimensional array
		Integer[][] myArray = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray));

		Integer[][] rotated = rotateMatrixClockwise(myArray);

		System.out.println("ROTATED ARRAY 90 degrees clockwise:");
		System.out.println(Arrays.deepToString(rotated));
		
		// define two dimensional array
		Integer[][] myArray1 = new Integer[][] { 
				{ 1, 2, 3, 4, 5 }, 
				{ 6, 7, 8, 9, 10 }, 
				{ 11, 12, 13, 14, 15 } 
			};

		System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myArray1));

		Integer[][] rotated1 = rotateMatrixCounterClockwise(myArray1);

		System.out.println("ROTATED ARRAY 90 degrees counter clockwise:");
		System.out.println(Arrays.deepToString(rotated1));

	}

	/**
	 * This method rotates the matrix 90 degrees clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

		for (int i = 0; i < matrix[0].length; ++i) {
			for (int j = 0; j < matrix.length; ++j) {

				
				rotated[i][j] = matrix[matrix.length - j - 1][i];
				
			}
		}

		return rotated;
	}
	
	/**
	 * This method rotates the matrix 90 degrees counter clockwise by using extra
	 * buffer.
	 */
	public static Integer[][] rotateMatrixCounterClockwise(Integer[][] matrix) {
		Integer[][] rotated = new Integer[matrix[0].length][matrix.length];

		for (int i = 0; i < matrix[0].length; ++i) {
			for (int j = 0; j < matrix.length; ++j) {
				
				rotated[i][j] = matrix[j][matrix[0].length - i - 1];
			}
		}

		return rotated;
	}

}

OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees clockwise:
[[11, 6, 1], [12, 7, 2], [13, 8, 3], [14, 9, 4], [15, 10, 5]]
SOURCE ARRAY: 
[[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]]
ROTATED ARRAY 90 degrees counter clockwise:
[[5, 10, 15], [4, 9, 14], [3, 8, 13], [2, 7, 12], [1, 6, 11]]