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 !!

Break The Integer

Problem:

Given an integer n, break it in smallest non-repeating subsets.

Eg 1: 5
1 1 1 1 1
2 1 1 1
3 1 1
4 1
5

Eg 2: 10
1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1
3 1 1 1 1 1 1 1
4 1 1 1 1 1 1
5 1 1 1 1 1
6 1 1 1 1
7 1 1 1
8 1 1
2 2 2 2 2
3 3 3 1
4 4 2
5 5
6 4
7 3
8 2
9 1
10

Time Complexity (for main logic):

n + n + n + n (for 4 loops)

i.e. 4n

i.e. O(n)

O(n) extra space.

Code:

public class SplitTheInteger {

 private int userInput;
 int[] temp;

 void start( int no ) {
  
  userInput = no;
  temp = new int[userInput];
  
  for (int i = 0; i < userInput; i++) {
   temp[i] = 1;
  }
  
  int len = userInput-1;
  
  /**
   * its working for userinput 5
   * 1 1  1  1  1
   * 2 1  1  1 -1
   * 3 1  1 -1 -1
   * 
   * 4 1 -1 -1 -1 //this is taken care by for
                 *  
                 * loop below while loop so to avoid redundancy i have 
   * made 'no-1'
   * 
   * 5
   */
  while (temp[0] != no-1 ) {
   algo();
   temp[0]++;
   temp[len] = -1;
   len--;
   
  }
  
  for (int i = 2; i <= userInput; i++) {
   /**
    * Suppose i = 3
    * UserInput = 10
    * 10/3 = 3
    * so print 3 three times and call done which will select 
    * such a number that will sum up UserInput i.e. 10
    */
   int m = userInput/i;
   int count = 0;
   while ( count != m ) {
    System.out.print( i + " ");
    count++;
   }
   if(i*count != userInput)
    done(count*i);
   System.out.println();
  }
  

  
 }
 
 
 private void algo() {
  // TODO Auto-generated method stub
  int z = temp[0];
  for (int k : temp) {
   if( k != -1)
    System.out.print(k + " ");
  }
  System.out.println();
  
    
 }


 private void done(int i) {
  // TODO Auto-generated method stub
  for (int j = 1; j <= userInput; j++) {
   if(j+i == userInput) {
    System.out.print(  j );
    break;
   }
   
  }
 }


 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new SplitTheInteger().start(10);
  
 }

}

Good Luck! & Happy Coding!!!

Turing Machine

Problem:

Design a TM to perform addition of 2 integers.

Background:

I am using TM with one way infinite tape

Time Complexity (for compute function):

O(m) where m is no1+no2

no1 is 1st operand for addition & no2 is second

Code:

import java.util.Scanner;

public class Adder {

 int head,sum;
 char[] tape;
 
 void init( ) {
  //one way infinite tape 
  tape = new char[37677];
  for (int i = 0; i < tape.length; i++) {
   tape[i] = 'B';
  }
  Scanner s = new Scanner(System.in);
  System.out.println("enter no1");
  int no1 = s.nextInt();
  System.out.println("enter no2");
  int no2 = s.nextInt();
  int p = 0;
  for (int i = 0; i < no1; i++,p++) {
   tape[i] = '0';
   
  }
  tape[p] = '1';
  p++;
  for (int i = 0; i < no2; i++,p++) { 
   tape[p] = '0';
  }
  compute();
 }
 private void compute() {
  // TODO Auto-generated method stub
  for (int i = 0; i < tape.length; i++) {
   if(tape[i] == '1') {
    tape[i] = '0';
   }
   if(tape[i] == 'B')
    reverse(i);
  }
 }
 
 private void reverse(int i) {
  // TODO Auto-generated method stub
  --i;
  tape[i] = 'B';
  for (int j = 0; j < tape.length; j++) {
   if(tape[j] != 'B')
    sum++;
  }
  System.out.println("sum is = " + sum);
  System.exit(0);
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new Adder().init();
 }

}

Cut The Rope

Problem:

Given a integer n, find all the subsets of n such that product obtained is maximum.

Eg 1: n = 10 {3 ,3 ,4} gives us 36 (highest product)

Eg 2: n = 20 {3 ,2 ,3 ,4 ,5 ,3} gives us 1080 (highest product)

Background:

At first glance i saw this problem as a inverted sum of subset problem, where we have given subsets as well as sum, but it is inverted because here we have just sum (n here) no subsets , we have to find all the subsets as a part of the solution.

After finding 1st subset store it somewhere, find next, now compare 1st and 2nd subsets product,

if 2nd subset-product > 1st subset-product

   store 2nd subset-product in some variable

repeat it until loops are exhausted.

Instead of solving it recursively i tried to solve it with tight for loops and a while loop.

Time Complexity:

O(n^2) and additional O(n) extra space.

Code:

import java.util.ArrayList;

public class CutTheRope {

 private int val;
 private int highval;
 private int m;
 /**
  * @param n
  */
 void start( int n ) {
  
  for (int i = 2; i < n-1; i++) {
   ArrayList myList = new ArrayList();
   myList.add(i);
   boolean isTrue = false;
   while (!isTrue) {
    
    
    for (int j = 2; j < n-1; j++) {
     int k = 0;
     for (Integer integer : myList) {
      k += integer.intValue();
     }
     //k+j+1 should not be equal to n ...
                                        //bcoz we r not staring loop from 1 its from 2
     if(k+j <= n && (k+j+1) != n)
      myList.add(j);
     if(k+j==n) {
      isTrue = true;
      break;
     }
    }
   }
   for (Integer integer : myList) {
    val = mult(integer.intValue());
    //System.out.print(integer + " ,");
   }
   //System.out.println();
   
   if (m >= 1) {
    if (highval < val)
     highval = val;
   }else {
   m++;
   highval = val;
   }
   k = -1;
  }
  if(highval != 0)
 System.out.println(highval);
   else
 System.out.println(n);
 }
 
 int k =-1;
 private int mult(int intValue) {
  // TODO Auto-generated method stub
  if(k == -1) {
   k = intValue;
  }
  else
  {
   k *= intValue;
  }
  return k;
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  new CutTheRope().start(22);
 }

}

Try it!

Good Luck.......