Thursday, February 23, 2012

Coin Problem(Foundations Of Algorithms)

Suppose we now have an integer n (that represents n coins) and only one of the coins is heavier than others. Suppose further that n is a power of 3 and you are allowed log base 3 n weighings to determine the heavier coin. Write an algorithm that solves this problem. Determine the time complexity of your algorithm.
/**
 *
 * @author RockHead
 */
public class Coins {

    //3 at the end for the worst case
    public static int[] coinArray = new int[]{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                                              1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,3};
    public static int count=0;
 
    public static void main(String[] args) {
        Coins coins = new Coins(); // new Coins object
        System.out.println(coins.getHeavierCoin(coins.weighGroup(coinArray)));
        System.out.println("The total count is :" +count);
        System.out.println("The predected count is: " +Math.log(coinArray.length)/Math.log(3));
        
        
    }

    private int[] weighGroup(int[] cArray)
    {
        if(cArray.length==3)
        {
            return cArray;
        }
        else
        {
            return weighGroup(getHeavierGroup(cArray));
        }
                 
             }
    
    
    //divides the the array into three groups andd adds equal number of elements into that group.
    private int[] getHeavierGroup(int[] cArray)
    {
        
            int arraySize=(cArray.length)/3;
            int[] groupOne=new int[arraySize];
            int[] groupTwo=new int[arraySize];
            int[] groupThree= new int[arraySize];
            
            //fill elements in each array
            int indexCount =0;
            for(int i=0;i getGroupSum(groupTwo))
            {
                return groupOne;
            }
            
            return groupTwo;
        
    }
     
    //gets the heavier coin within a group.
    private int getHeavierCoin(int[] finalGroup) {
        
        count++; // one weighing is done here
        if (finalGroup[0] == finalGroup[1])
        {
            return finalGroup[2];
        } 
        else if (finalGroup[0] > finalGroup[1])
        {
            return finalGroup[0];
        } 
        else 
        {
            return finalGroup[1];
        }
    }

    //get the sum of the group (weigh the coins)
    public int getGroupSum(int [] group) {
        int count =0;
        for (int i = 0; i < group.length; i++) {
            count += group[i];
        }
        return count;
    }
}


Lets try to find the complicity of this algorithm. we can see that each time the array is divided into 3 small groups and they are weighed (compared) so we have T(n/3)comparisons. After we have found the final group containing three elements we have one comparison. Therefore the complicity becomes T(n/3)+1. 

No comments:

Post a Comment