Coin change problem

Infinite no of {25,10,5,1} no. of ways to representing n.

// Comment

//Inputs:
  int[] denoms = {25,10,5,1};
  int[][] map = new int[100+1][denoms.length];
  System.out.println(makeChange(100, denoms, 0));
  System.out.println(makeChangeDP(100, denoms, 0, map));



// Recursive algorithm
 
 public static int makeChange(int amount, int[] denoms, int index)
 {
  if(index >= denoms.length-1) return 1;
  
  int denomAmount = denoms[index];
  int ways = 0;
  
  for(int i = 0; i*denomAmount <= amount; i++)
  {
   int amountRemaining = amount-i*denomAmount;
   ways += makeChange(amountRemaining, denoms, index+1);
  }
  
  return ways;
 }
 
// Dynamic programming.. map[amount+1][denoms.length]
 
 public static int makeChangeDP(int amount, int[] denoms, int index, int[][] map)
 {
  if(map[amount][index] != 0) return map[amount][index];
   
  if(index >= denoms.length-1) return 1;

  
  int denomAmount = denoms[index];
  int ways = 0;
  
  for(int i = 0; i*denomAmount <= amount; i++)
  {
   int amountRemaining = amount-i*denomAmount;
   ways += makeChange(amountRemaining, denoms, index+1);
  }
  map[amount][index] = ways;
  return ways;
 }

Quick sort in Java

Quick sort in Java

// Comment Quick Sort
 


 public static void quick_sort(int[] a) {
  int len = a.length;

  if (a == null || len == 0)
   throw new IllegalArgumentException("Null/Invalid Input");

  quick_sortUtil(a, 0, len - 1);

 }

 private static void quick_sortUtil(int[] a, int l, int r) {

  if (l > r)
   return;

  int p = pivot(a, l, r);
  quick_sortUtil(a, l, p - 1);
  quick_sortUtil(a, p + 1, r);

 }

 private static int pivot(int[] a, int l, int r) {

  int x = a[r], j, i;
  for (i = l, j = l; i < r && j < r; i++) {
   if (a[i] <= x) {
    swapArr(a, i, j);
    j++;
   }
  }

  swapArr(a, j, r);

  return j;
 }

 private static void swapArr(int[] arr, int i, int j) {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
 }

Tets

// Comment
public class Testing {
public Testing() {
}
 
public void Method() {
/* Another Comment
on multiple lines */
int x = 9;
}
}

Merge sort in JAVA : Top-down implementation using lists

// Comment Merge Sort for array

 public static void mergeSort(int[] A) {
  if (A == null)
   throw new NullPointerException("Input doesn't exist.");

  int len = A.length;

  if (len == 0)
   throw new IllegalArgumentException("No input from user.");

  mergeSortUtil(A, 0, len - 1);
 }

 private static void mergeSortUtil(int[] a, int l, int r) {

  if (l >= r)
   return;

  int m = l + (r - l) / 2;

  mergeSortUtil(a, l, m);
  mergeSortUtil(a, m + 1, r);

  merge(a, l, m, r);

 }

 private static void merge(int[] a, int l, int m, int r) {

  int k = 0, i, j;
  int[] b = new int[(r - l) + 1];

  for (i = l, j = m + 1; i <= m && j <= r;) {
   if (a[i] < a[j])
    b[k++] = a[i++];
   else
    b[k++] = a[j++];
  }

  while (i <= m)
   b[k++] = a[i++];

  while (j <= r)
   b[k++] = a[j++];

  for (int s = l, f = 0; f < b.length; s++) {
   a[s] = b[f++];
  }
 }

Top-down implementation using lists :

function merge_sort(list m)
    // Base case. A list of zero or one elements is sorted, by definition.
    if length(m) <= 1
        return m

    // Recursive case. First, *divide* the list into equal-sized sublists.
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right

    // Recursively sort both sublists.
    left = merge_sort(left)
    right = merge_sort(right)
    // *Conquer*: merge the now-sorted sublists.
    return merge(left, right)

In this example, the merge function merges the left and right sublists.

function merge(left, right)
    var list result
    // assign the element of the sublists to 'result' variable until there is no element to merge. 
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
           // compare the first two element, which is the small one, of each two sublists.
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

 public static LNode mergeSortList(LNode list) {
  int len = length(list);
  if (len <= 1)
   return list;

  LNode left = list, right = null;

  right = addLeftList(left, len);

  left = mergeSortList(left);
  right = mergeSortList(right);
  LNode res = merge(left, right);

  return res;
 }

 private static int length(LNode list) {
  int len = 0;
  for (LNode curr = list; curr != null; curr = curr.next)
   len++;
  return len;
 }

 private static LNode addLeftList(LNode list, int n) {
  int m = n / 2;
  LNode curr = list;
  for (int i = 0; curr != null && i < m - 1; i++)
   curr = curr.next;
  list = curr.next;
  curr.next = null;
  return list;
 }

 private static LNode merge(LNode left, LNode right) {
  LNode result = null, curr = null, tmp = null;
  while (left != null && right != null) {
   if (left.val < right.val) {
    curr = left;
    left = left.next;
   } else {
    curr = right;
    right = right.next;
   }

   if (result == null) {
    result = curr;
    tmp = curr;
   } else {
    tmp.next = curr;
    tmp = tmp.next;
   }
  }

  if (left != null)
   tmp.next = left;
  if (right != null)
   tmp.next = right;

  return result;
 }
 

Write an algorithm such that if an element in an M*N matrix is 0, its entire row and column set to zero.

Program:

Connect n ropes with minimum cost: JAVA

Following is complete algorithm for finding the minimum cost for connecting n ropes.
Let there be n ropes of lengths stored in an array len[0..n-1]
1) Create a min heap and insert all lengths into the min heap.
2) Do following while number of elements in min heap is not one.
……a) Extract the minimum and second minimum from min heap
……b) Add the above two extracted values and insert the added value to the min-heap.
3) Return the value of only left item in min heap.

 For 5,6,7,8 is 11+15+26=52 and not 55.

References:
http://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

Maximum Sum Path in Two Arrays

Given two sorted arrays such the arrays may have some common elements. Find the sum of the maximum sum path to reach from beginning of any array to end of any of the two arrays. We can switch from one array to another array only at common elements.

Program:

Reference:
http://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/

Find if there is a subarray with 0 sum

// Print starting and ending indexes of all subarrays with 0 sum.

static boolean isExistSumZero(int[] arr){
int len = arr.length;

if(len == 0) return false;
int sum = 0, start=0, end=0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i< len; i++)
{
sum += arr[i];

if(arr[i] == 0 || sum == 0 || map.get(sum) != null)
{
if(map.get(sum) != null)
start = map.get(sum)+1;
else if(arr[i] == 0) start = i;
else start = 0;
end = i;
System.out.println(start +","+ end);
return true;
}

map.put(sum, i);
}
return false;
}

References:
http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/

Search in a row wise and column wise sorted matrix

 Given a matrix with row sorted and column sorted, find the number given:

static boolean searchGivenNo(int[][] arr, int x){
int rows = arr.length;
if(rows == 0) return false;

int cols = arr[0].length;

for(int i = 0; i<rows; i++)
{
for(int j = cols-1; j>=0; j--)
{
if(arr[i][j] == x) return true;

if(arr[i][j] < x) break;
}
}
return false;
}


References:
http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

Smallest subarray with sum greater than a given value

static int findSmallestSubArrayLen(int[] arr, int x){

int len = arr.length;

int sum = 0, min = len, r = 0,rear = 0,front = 0;

for(int i = 0; i<len; i++)
{
sum += arr[i];
if(sum > x)
{
for(; r <= i; )
{
if(sum > x)
{
if(min > i-r+1){
min = i-r+1;
rear = r;
front = i;
}
sum -= arr[r++];
}else break;
}
}
}
if(min != len){
while(rear<=front){
System.out.print(arr[rear++]+",");
}
return min;
}

else return -1;
}

Reference:

http://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

Create a matrix with alternating rectangles of O and X

Reference:

http://www.geeksforgeeks.org/create-a-matrix-with-alternating-rectangles-of-0-and-x/

Spiral traversal of 2D Matrix

Please be careful of m*n and n*n matrix.

Boundary conditions are important.

static void spiralTraversal(int[][] a){

int r = a.length;
int c = a[0].length;

//System.out.println(c);

int r1 = 0, r2 = r-1, c1 = 0, c2 = c-1;

while(r1 <= r2 && c1 <= c2)
{
//System.out.println(r1+","+c2);
for (int i = r1; i <= c2; i ++)
{
System.out.print(a[r1][i]+ " ");
}
r1++;

for(int i = r1; i<= r2 && r1 <= r2; i++)
{
System.out.print(a[i][c2]+ " ");
}

c2--;

for(int i = c2; i>=c1 && c1 <= c2; i--)
{
System.out.print(a[r2][i]+ " ");
}

r2 --;

for(int i = r2; i>=r1; i--)
{
System.out.print(a[i][c1]+ " ");
}
c1++;



}

Find the k-th Smallest Element in the Union of Two Sorted Arrays

Find the minimum element in a sorted and rotated array

/*
-- Base Conditions of array
-- Divide and Conquer Algorithm
-- Find middle element
-- Condition for return result
-- Condition for return left sub array
-- Condition for return right sub array
-- return result if except all test cases
*/

static int minimumElement(int[] a, int l, int r){
if (a == null || r == -1) return -1;
if(l == r) return a[l];

int m = l + (r-l)/2;

if((m-1)>=0 && a[m-1] > a[m]) return a[m];

if(a[l] > a[m]) return minimumElement(a, l, m-1);

else if(a[m] > a[r]) return  minimumElement(a, m+1, r);

return a[0];
}

References:
http://www.geeksforgeeks.org/find-minimum-element-in-a-sorted-and-rotated-array/

Merge k sorted arrays

// define max value for min heap when array doesn't have any more element
public static final int MAX_VALUE = 10000;

static int[] mergeKArray(int a[][], int row, int col){
int count = 0;
if(row == 0 || row == 1) return a[0];
// declare final merged sorted array
int mergeArr[] = new int[row*col];

// allocation of heapNode array which has size no of row times.
heapNode[] hn = new heapNode[row];

for (int i = 0; i<row; i++)
{
hn[i] = new heapNode(a[i][0], 1, i);
//hn[i].key = a[i][0];
//hn[i].index = 1;
//hn[i].n = i;
}

// convert heapNode array to minheap
minHeap(hn);

heapNode minKeyNode;

for(int i = 0; i< row*col; i++)
{
minKeyNode = minValueHeap(hn);

mergeArr[count++] = minKeyNode.key;

if(minKeyNode.index < a[minKeyNode.n].length)
{
minKeyNode.key = a[minKeyNode.n][minKeyNode.index];
minKeyNode.index++;
}else minKeyNode.key = MAX_VALUE;

hn[0] = minKeyNode;

minHeapify(hn, 0, row);
}
return mergeArr;
}

private static void minHeap(heapNode[] hn) {
int n = hn.length;
if(n == 0 || n == 1) return;
for(int i=n/2; i>=0; i--)
{
minHeapify(hn,i,n);
}
}

private static void minHeapify(heapNode[] hn, int i, int n){
int minIndex = i;
int l = left(i);
int r = right(i);
if(l < n && (hn[l].key < hn[i].key))
{
minIndex = l;
}
if(r < n && (hn[minIndex].key > hn[r].key))
{
minIndex = r;
}

if(minIndex != i)
{
swap(hn, minIndex, i);
minHeapify(hn, minIndex, n);
}
}

private static void swap(heapNode hn[], int minIndex, int i){
heapNode tmp = hn[i];
hn[i] = hn[minIndex];
hn[minIndex] = tmp;
}


private static heapNode minValueHeap(heapNode hn[]){
return hn[0];
}

private static int right(int i) {
return 2*i+2;
}

private static int left(int i) {
return 2*i+1;
}


References:
http://www.geeksforgeeks.org/merge-k-sorted-arrays/

Count all distinct pairs with difference equal to k

-- If difference of curr and prev index value is equal to k, increment count by 1
-- curr greater than prev and difference of values less than k, increment curr.
-- curr greater than prev and difference of values legreater than k, increment prev.


static int countPairsWithDiffK(int a[], int k){
int n = a.length;
if(n == 0 || n == 1) return 0;
int count = 0, rem_curr = 0;
Arrays.sort(a);
for(int curr = 1, prev = 0; curr < n; )
{
if(a[curr] - a[prev] == k)
{
if(a[curr] != a[rem_curr])
{
System.out.println(a[curr]+", "+a[prev]);
count ++;
}
rem_curr = curr;
curr ++;
}
else if(curr > prev && a[curr] - a[prev] < k)
{
curr ++;
}else if(curr > prev && a[curr] - a[prev] > k)
{
prev ++;
}else curr ++;


}
return count;
}


References:
http://www.geeksforgeeks.org/count-pairs-difference-equal-k/

Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

Idea is to multiply each array element  with n(no of elements) and get remainder of final array

static void rearrangeArr(int a[]){

int n = a.length;
if(n == 0 || n == 1) return;

for(int i = 0 ; i < n; i++)
{
a[i] = a[i]*n;
}

for(int i = 0; i < n; i++)
{
a[i] = a[i] + a[a[i]/n] /n;
}
for(int i = 0; i < n; i++)
{
a[i] = a[i]%n;
System.out.print(a[i] +" ");
}
}


References:
http://www.geeksforgeeks.org/rearrange-given-array-place/