Code 4 Life

Sunday, July 19, 2015

Binary Search

Array must be sorted first before searching.

example
Sorted array: L = [1, 3, 4, 6, 8, 9, 11]
Target value: X = 4
Compare X to 6. X is smaller. Repeat with L = [1, 3, 4].
Compare X to 3. X is larger. Repeat with L = [4].
Compare X to 4. X equals 4, so the position is returned.

public class BinarySearch{

     public static void main(String []args){
        // Binary search must be sort first
        int[] array = new int[]{10,20,50,53,68,81,92,105,110,200,280,360,361,386,400};
        
        if(binSearch(array,81) == -1)
            System.out.print("not found");
        else
            System.out.print("found at index "+ binSearch(array,81));
     }
     
     public static int binSearch(int[] arr, int search){
         int first =0;
         int last = arr.length-1;
         int mid=0;
         
         while(first<=last){
             mid = (first+last)/2;
             
             if(arr[mid] == search)
                return mid;
             else if (arr[mid]<search)
                first = mid+1;
             else
                last = mid-1;
         }
         
         return -1;
     }
}

Monday, July 13, 2015

Longest Palindrome in String

Longest Palindromic substring. Given a string, find the longest substring which is palindrome. For example, if the given string is "forgeeksskeegfor", the output should be "geeksskeeg".

public class PalinLong{

     public static void main(String []args){
        
        String s = "forgeeksskeegfor";
        String longest="";
        for(int x=0;x<s.length();x++){
            for(int y=x+1;y<=s.length();y++){
                String t = s.substring(x,y);
                if(isPalin(t)){
                    if(t.length()>longest.length()){
                        longest = t;
                    }
                }
            }   
        }
        
        System.out.print(longest);
     }
     
     public static boolean isPalin(String s){
         String rev="";
         
         for(int x=s.length()-1;x>=0;x--){
             rev = rev + s.charAt(x);
         }
         
        if(rev.equals(s))
            return true;
        else
            return false;
     }
}

Monday, June 29, 2015

Convert Numbers to Words

Convert numbers to words..
ex:
100 = one hundred
101 = one hundred and one

public class NumberToWordsConverter {

   final private static String[] units = {"Zero","One","Two","Three","Four",
  "Five","Six","Seven","Eight","Nine","Ten",
  "Eleven","Twelve","Thirteen","Fourteen","Fifteen",
  "Sixteen","Seventeen","Eighteen","Nineteen"};
   final private static String[] tens = {"","","Twenty","Thirty","Forty","Fifty",
  "Sixty","Seventy","Eighty","Ninety"};
   
   public static void main(String[] args){
      System.out.print(convert(312));
   }

   public static String convert(int i) {
      if( i < 20)
         return units[i];
      if( i < 100) 
         return tens[i/10] + ((i % 10 > 0)? " " + convert(i % 10):"");
      if( i < 1000) 
         return units[i/100] + " Hundred" + ((i % 100 > 0)?" and " + convert(i % 100):"");
      if( i < 1000000) 
         return convert(i / 1000) + " Thousand " + ((i % 1000 > 0)? " " + convert(i % 1000):"") ;

      return convert(i / 1000000) + " Million " + ((i % 1000000 > 0)? " " + convert(i % 1000000):"") ;
   }

}

Pascal Triangles

Pascal’s triangle is a set of numbers arranged in the form of a triangle. Each number in a row is the sum of the left number and right number on the above row. If a number is missing in the above row, it is assumed to be 0. The first row starts with number 1.

Ex: The following example is a pascal with 7 rows

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1

How it work?
Each row begins and ends with the number one. The remaining numbers are obtained by summing the two numbers that lie directly above that number on the previous row and the number that follows it. So, in order to find the numbers in the nth row of the triangle, we need the values of the (n-1) the row. Let's say that we have computed the fourth row - 1 3 3 1. Now, the fifth row has five elements. The first and the last element would be one. The remaining elements would be (1+3), (3+3), (3+1) = 4, 6, 4. So, the complete fifth row would be 1 4 6 4 1.

public class Pascal
{ 
    public static void main(String[] args)
    { 
        int ROW = 7;
        int max=0;
        int[][] pascal  = new int[ROW +1][];

        pascal[1] = new int[1 + 2];
        pascal[1][1] = 1;

        for (int i = 2; i <= ROW; i++)
        {
            pascal[i] = new int[i + 2];
            for (int j = 1; j < pascal[i].length - 1; j++)
            {
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
                String str = Integer.toString(pascal[i][j]);
                int len = str.length();
                if (len > max)
                    max = len;
            }
        }
        
        // Display
        for (int i = 1; i <= ROW; i++)
        {                
            for (int k = ROW; k > i; k--)
                System.out.format("%-" + max + "s", " ");
            for (int j = 1; j < pascal[i].length-1; j++)                      
                System.out.format("%-" + (max + max) + "s",  pascal[i][j]);
            System.out.println();
        }
        
    }
}

Bubble Sort

How its work?
An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

public class BubbleSort {
        public static void main(String[] args) {
                int intArray[] = new int[]{51,1,61,7,55,90,25,99,91,15,35};
               
                System.out.println("Array Before Bubble Sort");
                for(int i=0; i < intArray.length; i++){
                        System.out.print(intArray[i] + ", ");
                }
                System.out.println();
                bubbleSort(intArray);
        }
 
        private static void bubbleSort(int[] intArray) {
           int n = intArray.length;
           int temp = 0;
           for(int i=0; i < n; i++){
               for(int j=1; j < (n-i); j++){
                  if(intArray[j-1] > intArray[j]){
                     temp = intArray[j-1];
                     intArray[j-1] = intArray[j];
                     intArray[j] = temp;             
                   }      
                   display(intArray);
                }
           }
        }
        
        private static void display(int[] intArray){
            for(int i=0; i < intArray.length; i++){
                    System.out.print(intArray[i] + ", ");
                }
                System.out.println();
        }
}

Trailing Zero of Factorial Numbers

Count trailing 0's from n factorial integers
ex: 10! = 3628800 = 2 trailing 0's

Input:
3
44
12
10

Output:
Case#1: 9
Case#2: 2
Case#3: 2

import java.util.*;
import java.math.*;

public class trailingzero{
   public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      
      int cases=scan.nextInt();
      int[] num = new int[cases];
      
      for(int x=0;x<cases;x++)
         num[x] = scan.nextInt();
      
      for(int x=0;x<cases;x++){
         int count =0;                
         String sfact = ""+factorial(num[x]);
         for(int y=sfact.length();y>=0;y--)
         {
            if(!sfact.substring(y-1,y).equalsIgnoreCase("0"))
               break;
            else
               count++;
         }                  
         System.out.println("Case#"+(x+1)+": "+count);
      }
   }
   //this function for factorial number >=100
   public static BigInteger factorial(int number){
       BigInteger fact = new BigInteger("1"); 
       for ( int i = 2; i <= number; i++)
         fact = fact.multiply(BigInteger.valueOf(i));
       
       return fact;
   }
   
   
}

Count 1's between numbers

Count how many 1's in range of numbers
ex: 1 to 20 equals to twelve 1's

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

import java.util.*;

public class CountOne{
   public static void main(String[] args){  
      int n=20;
      long i = 0, j = 1;
      long count = 0;
      for (i = 1; i <= n; i ++)
      {
          j = i;
          while (j != 0)
          {
              if (j % 10 == 1)
                  count ++;
              j /= 10;
          }
      }
      System.out.print(count); 
   }
}

Pages