Friday 27 December 2013

The Mean, Median & Mode Revisited

Problem:


Given a 2 sorted array find mean, median & mode

Solution:


1) Two Sorted arrays can be merged in O(n) time.
2) Calculating mean is simple i.e.
        a) calculate k = summation of mergedarray[i]
        b) do k/mergearray.length
        c) display k as mean value
3) Calculating Median
        a) In case total no of element is ODD, int m = mergedarray.length/2, then display m as median value
        b) In case total no of element is EVEN, int m = mergedarray.length/2,
            int val = (mergedarray[m]+mergedarray[--m])/2
            display val as median
4) Calculating Mode is simple i.e.
     -- find number which  occurs max number of times.

Code:

     
import java.util.ArrayList;


public class MyDS {

 int[] no,count;
 int ptr = 0;
 public MyDS(int n) {
  no = new int[n];
  count = new int[n];
 }
 
 public void add(int val, int occ) {
  no[ptr] = val;
  count[ptr] = occ;
  ptr++;
 }
 
 public ArrayList getModeValue() {
  int max = 0,z=0;
  ArrayList k = new ArrayList();
  for (int i = 0; i < count.length; i++) {
   if( count[i] > max) {
    max = count[i];
    z = i;
   }
  }
  k.add(no[z] + " " + max);
  for (int i = 0; i < count.length; i++) {
   if( count[i] == max && z != i ) {
    if(!k.contains(no[i] + " " + max))
    k.add(no[i] + " " + max);
   }
  }
  return k;
 }
 
 

}



import java.util.ArrayList;

public class Merge2SortedArray {

 int arr1[],arr2[],farr[];
 int ptr1,ptr2,fptr;
 
 void init(int[] a, int[] b ) {
  arr1 = a;
  arr2 = b;
  farr = new int[arr1.length+arr2.length];
  merge();
 }
 
 private void merge() {
  // TODO Auto-generated method stub
  /**
   * while-loop to tackle merging of sorted arrays of unequal length
   * for-loop is ok for merging equal length sorted array.
   * 
   */
  while (ptr1 <= arr1.length || ptr2 <= arr2.length) {
   if(arr1[ptr1] < arr2[ptr2]) {
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
   }else if( arr2[ptr2] < arr1[ptr1] ) {
    farr[fptr] = arr2[ptr2];
    fptr++;
    ptr2++;
   }else {
    farr[fptr] = arr1[ptr1];
    fptr++;
    farr[fptr] = arr1[ptr1];
    fptr++;
    ptr1++;
    ptr2++;
   }
   if(ptr1 >= arr1.length) {
    copyArr2();
    break;
   }else if( ptr2 >= arr2.length) {
    copyArr1();
    break;
   }
  }

  median();
  mean();
  MyDS ds = new MyDS(farr.length);
  
  for (int i = 0; i < c; i++) {
   int occurence = mode(farr[i]);
   ds.add(farr[i],occurence);
  }
  
  displayMode(ds);
 }

 private void displayMode(MyDS ds) {
  // TODO Auto-generated method stub
  ArrayList modeValue = ds.getModeValue();
  System.out.println("And the mode value is ");
  for (String string : modeValue) {
   System.out.println(string);
  }
 }

 private int mode(int k) {
  // TODO Auto-generated method stub
  int z = 0;
  for (int i = 0; i < c; i++) {
   if(farr[i] == k)
    z++;
  }
  return z;
 }

 private void mean() {
  // TODO Auto-generated method stub
  int sum =0;
  for (int i = 0; i < c; i++) {
   sum += farr[i];
  }
  System.out.println("And mean is " + sum/c);
 }
 
 int c = 0;
 private void median() {
  // TODO Auto-generated method stub
  
  for (int k : farr) {
   if(k != 0) {
    System.out.print(k + " ");
    c++;
   }
  }
  
  System.out.println("\n" + "And the median is ");
  
  if((c%2)==0) {
   int med = c/2;
   avgingMideans(med,--med);
  } else
   System.out.println(farr[((c+1)/2)-1]);
 }

 private void avgingMideans(int c2, int c3) {
  // TODO Auto-generated method stub
  int k = (farr[c2]+farr[c3])/2;
  System.out.println(k);
 }

 private void copyArr1() {
  // TODO Auto-generated method stub
  for (int i = ptr1; i < arr1.length; i++) {
   farr[fptr] = arr1[i];
   fptr++;
  }
 }

 private void copyArr2() {
  // TODO Auto-generated method stub
  for (int i = ptr2; i < arr2.length; i++) {
   farr[fptr] = arr2[i];
   fptr++;
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] a = {6,6};
  int[] b = {2,4};
  new Merge2SortedArray().init(a  ,b);
 }
}
GOOD LUCK!  Merry Christmas & Happy New Year !!

No comments:

Post a Comment