Maximum contiguous product in an Array

Given an array of natural numbers (+ve, 0, -ve) find the maximum product of continuous elements.


input  : a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
output : 3360(From index positions 7 to 12)

class MaximumContiguousProduct {

 public static void main(String[] args) {
  int[] a = { 11, 4, 5, -2, 0, -3, -4, 4, 2, 3, 5, -7 };
  int product = getMaximumProduct(a);
  System.out.println(product);
 }

 /**
  * Track zero positions and calculate maximum product till zero
  * 
  * @param a
  * @return
  */
 public static int getMaximumProduct(int[] a) {

  if (a == null || a.length == 0)
   return 0;

  int start = 0;
  int maxSubArrayProduct = 0;
  int maxProduct = -3421545;
  for (int i = 0; i < a.length; i++) {
   if (a[i] == 0) {// if ith element is zero then send i-1 element as
    // end position
    maxSubArrayProduct = getMaxProductInSubArray(a, start, i - 1);
    start = i + 1;// skip the ith element.
   } else if (i == a.length - 1) {
    maxSubArrayProduct = getMaxProductInSubArray(a, start,
      a.length - 1);
   }
   if (maxSubArrayProduct > maxProduct)
    maxProduct = maxSubArrayProduct;
  }
  return maxProduct;
 }

 // in this sub array check if array contains even number of -ve numbers or
 // odd.
 // If it is even number,max product is product of all numbers
 // else we will get two products.
 private static int getMaxProductInSubArray(int[] a, int start, int end) {

  if (a == null || a.length == 0 || start > end)
   return 0;
  else if (start == end)
   return a[start];

  int numberOfNegativeNumbers = 0;
  int totalProduct = 1;
  for (int i = start; i <= end; i++) {
   if (a[i] < 0)
    numberOfNegativeNumbers++;
   totalProduct = totalProduct * a[i];
  }

  if (numberOfNegativeNumbers % 2 == 0)// handling case for even number of
   // negative numbers.
   return totalProduct;

  // for odd number of -ve numbers,total prod value is -ve.calculate prod1
  // and prod2
  int prod1 = 1;
  int i = start;
  while (a[i] > 0) {// calculating till we trace first -ve number
   prod1 = prod1 * a[i];
   i++;
  }
  int prodRem1 = totalProduct / (prod1 * a[i]);

  int prod2 = 1;
  i = end;
  while (a[i] > 0) {// calculating till we trace first -ve number
   prod2 = prod2 * a[i];
   i--;
  }

  int prodRem2 = totalProduct / (prod2 * a[i]);

  return prodRem1 > prodRem2 ? prodRem1 : prodRem2;
 }
}

Is given point lies inside a triangle

Given three points A,B,C which forms a triangle and a point P.Now check whether point P lies inside the triangle formed by ABC.
Solution : Trick is to check for each line of a triangle formed by any two of A,B,C whether point P and remaining point lies on same side or opposite side.If they lies on same side,it will form a triangle.

for line AB----->C,P should be on same side.
for line BC----->A,P should be on same side.
for line CA----->B,P should be on same side.

If it satisfies above three conditions,we can say point is inside the triangle.

Now how do we check whether two points lie on same side of a line?
Substitute the given points in the line and check if they are yielding result with same sign.
ex: eq is Px+Qy+R=0;
for points (X1,Y1),(X2,Y2),substitute these points in the equation..
after substituting,if  PX1+QY1+R and PX2+QY2+R have the same sign,both points are on same side else they are on opposite side.

Method 2 : Calculate areas of triangles ABP,BCP,ACP and ABC.if sum of these 3 triangle areas is equal to the main triangle area,point is inside the triangle.It is very complex to calculate the area of the triangle and if area is float value, comparison will be difficult(doesn't give accurate result).

Mirror image of a tree in iterative way

Algorithm : push all nodes of a binary tree into a stack.Pop element by element from the stack and exchange left and right pointers of the popped node.

void mirror(node* root)
{
        if(root == NULL) return;
        node *temp;
        node *q[100] = {NULL};
        int i,j;
        i = j = 0;
        
        while(root)
        {
                temp = root->left;
                root->left = root->right;
                root->right = temp;
                //printf("%d %d",root->left->data,root->right->data);
                if(root->left)
                        q[i++] = root->left;
                if(root->right)
                        q[i++] = root->right;
                root = q[j++];
        }
}

Refer for complete code : http://www.ideone.com/NyAmw

Contiguous subarray with sum zero

Given an array with + and - numbers, including zero, Write an algorithm to find all the possible sub arrays which sum up to zero.
For example, if given array is
20 , -9 , 3 , 1, 5 , 0, -6 , 9
Then possible sub arrays are:
-9, 3, 1, 5
0
1, 5, 0, -6
Solution: 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ZeroSumContiguousSubArray {

 public static void main(String[] args) {
  int[] a = {20 , -9 , 3 , 1, 5 , 0, -6 , 9};
  System.out.println("actual array elements are :");
  printArray(a,0,a.length-1);  
  getSubArraysWithZeroSum(a);
 }

 private static void getSubArraysWithZeroSum(int[] a) {
  
  if(a==null || a.length==0) return;
    
  
  //construct a temporary array with sums
  int[] temp = new int[a.length+1];
  //add '0' as first element in the temporary array to simplify the code and cover edge conditions.
  temp[0] = 0;
  temp[1]=a[0];
  for(int i=2;i<temp.length;i++){   
   temp[i]=temp[i-1]+a[i-1];
  }
  
  //construct a hash map with sum as keys and list of positions as values;
  Map<Integer,List<Integer>> map = new HashMap<Integer, List<Integer>>();
  
  for(int i=0;i<temp.length;i++){
   if(map.get(temp[i])==null){
    List list = new ArrayList<Integer>();
    list.add(i);
    map.put(temp[i], list);
   }else{
    List list = map.get(temp[i]);
    list.add(i);
    map.put(temp[i], list);
   }
  }   
   //Retrieve the lists from map and check if list size is greater than one.
   //if the list size greater than one,get combinations and call print methods
  for(List<Integer> list : map.values()){
   if(list.size()>1){
    getCombinations(a,list);
   }
  }
 }

 private static void getCombinations(int[] a, List<Integer> list) {
  //select two elements from the list and call print method with element positions as starting and ending
  for(int i=1;i<list.size();i++){//here we can modify the code to select any two elements instead of side by side elements so that it prints all combinations
   printArray(a, list.get(i-1), list.get(i)-1);
  }  
 }
 
 private static void printArray(int[] a,int start,int end) {
  System.out.println();
  for(int i=start;i<=end;i++){
   System.out.print("  "+a[i]);
  }
  System.out.println();
 }  
}

Nuts and Bolts problem

You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut.


http://tech-queries.blogspot.com/2011/01/nuts-and-bolts-algorithm.html
Refer : http://valis.cs.uiuc.edu/~sariel/teach/2004/b/webpage/lec/15_rand_notes.pdf

Ten Ways to Check if an Integer Is a Power Of Two in C

http://www.exploringbinary.com/ten-ways-to-check-if-an-integer-is-a-power-of-two-in-c/

Count number of min elements on right of each element in an array

You have an array like ar[]= {1,3,2,4,5,4,2}. 
You need to create another array  ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}

Algorithm :
1)Conside original array a[]
2)Construct a sorted list with the array elements(O(nlogn))
3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search.
  -position in the sorted list returns the number of elements in the less than the current element on right side.
  -after remove the current element from the sorted list.
PS: list is preferred datastructure because there are so many insertion and deletion operations.

public static int[] createLowArray(int[] a) {
  if (a == null || a.length == 0)
   return null;
  int length = a.length;
  int[] minArray = new int[length];

  // constructing a list from the array elements
  ArrayList<Integer> list = new ArrayList<Integer>();
  for (int i = 0; i < a.length; i++) {
   list.add(a[i]);
  }
  // sort the array 1 2 2 3 4 4 5
  Collections.sort(list);

  // traverse across all elements of the array and do the binary search in
  // the sorted list for it's position
  // after getting position(right occurrence),remove the element from the sorted list
  for (int i = 0; i < length; i++) {
   int pos = Collections.binarySearch(list, a[i]);
   // getting the right occurrence of the element position
   // we can iterate through elements to modify binary search to return
   // right occurrence
   while (pos < list.size()-1  && list.get(pos + 1) == list.get(pos)) {    
     pos++;    
   }
   minArray[i] = pos;
   list.remove(pos);// remove the element from the sorted list
  }
  return minArray;
 }

Note : Position count starts from 0. 

ex: {1,2,3,4} ...position of '1' is zero............

In the below approach,we are checking element position in the modified list(after deletion operation in the previous iteration).

given array is : ar[]= {1,3,2,4,5,4,2}.

construct a list with array elements and sort it.Now list contains :1,2,2,3,4,4,5

Now traverse through array elements from i=0 to n-1(start to end)

store result in result[] array.

list is 1-2-2-3-4-4-5

for i=0, a[0]=1,search for a[0] position in the list(right occurrence).a[0]=1 position in list is '0'

    add '0' to result.===>result[0]=0;

remove the element a[0] from the list.now list contains 2-2-3-4-4-5

for i=1,a[1]=3,search for a[1] position in the list(right occurence).a[1]=3 position in list is '2'

  add '2' to result====>result[1]=2

remove the element a[1] from the list.now list contains 2-2-4-4-5

for i=2,a[2]=2,search for a[2] position in the list(right occurence).a[2]=2 position in list is '1'

  add '1' to result====>result[2]=1

remove the element a[2] from the list.now list contains 2-4-4-5

for i=3,a[3]=4,search for a[3] position in the list(right occurence).a[3]=4 position in list is '2'

  add '2' to result====>result[3]=2

remove the element a[3] from the list.now list contains 2-4-5

for i=4,a[4]=5,search for a[4] position in the list(right occurence).a[4]=5 position in list is '2'

  add '2' to result====>result[4]=2

remove the element a[4] from the list.now list contains 2-4

for i=5,a[5]=4,search for a[5] position in the list(right occurence).a[5]=4 position in list is '1'

  add '1' to result====>result[5]=1

remove the element a[5] from the list.now list contains 2

for i=6,a[6]=2,search for a[6] position in the list(right occurence).a[6]=2 position in list is '0'

  add '0' to result====>result[6]=0

remove the element a[6] from the list.now list is empty.

resultant array contains : 

from all conditions : 

add '0' to result.===>result[0]=0;

add '2' to result====>result[1]=2

add '1' to result====>result[2]=1

add '1' to result====>result[3]=2

add '2' to result====>result[4]=2

add '1' to result====>result[5]=1

add '0' to result====>result[6]=0

expected result   {0,2,1,2,2,1,0}

actual result ==>{0,2,1,2,2,1,0}

 If we use java arraylist,it will find the element position in O(logn) time complexity using binarysearch.

Arraylist implements RandomAccess marker interface which facilitate it to find in O(long)

Refer : http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#binarySearch(java.util.List, T)

This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). 

But problem of using arrayList is,when ever an element is removed from the list,all subsequent has to be moved.

If the given array is already sorted,it will reach worst case O(n*n).Because we need to move all elements as we find element to be removed at starting position.




Simple approach : Start with two loops,for each element count the number of minimum elements which are less than the element