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. 

fizzbuzz java solution for codeEval.com

Fizz Buzz

Description:

Players generally sit in a circle. The player designated to go first says the number "1", and each player thenceforth counts one number in turn. However, any number divisible by 'A' e.g. three is replaced by the word fizz and any divisible by 'B' e.g. five by the word buzz. Numbers divisible by both become fizz buzz. A player who hesitates or makes a mistake is either eliminated.

Write a program that prints out the the pattern generated by such a scenario given the values of 'A'/'B' and 'N' which are read from an input text file. The input text file contains three space delimited numbers i.e. A, B, N. The program should then print out the final series of numbers using 'F' for fizz, 'B' for 'buzz' and 'FB' for fizz buzz.

Input sample:

Your program should read an input file (provided on the command line) which contains multiple newline separated lines. Each line will contain 3 numbers which are space delimited. The first number is first number to divide by ('A' in this example), the second number is the second number to divide by ('B' in this example) and the third number is where you should count till ('N' in this example). You may assume that the input file is formatted correctly and is the numbers are valid positive integers.e.g.

3 5 10
2 7 15
Output sample:

Print out the series 1 through N replacing numbers divisible by 'A' by F, numbers divisible by 'B' by B and numbers divisible by both as 'FB'. Since the input file contains multiple sets of values, your output will print out one line per set. Ensure that there are no trailing empty spaces on each line you print.e.g.


1 2 F 4 B F 7 8 F B
1 F 3 F 5 F B F 9 F 11 F 13 FB 15




solution: in java

import java.io.*;

import java.util.*;

public class fizzbuzz {

public static void main(String[] args) throws IOException

{

Scanner console = new Scanner(new FileReader(args[0]));
while(console.hasNext())

{
int first=console.nextInt();
int second =console.nextInt();
int third =console.nextInt();

for(int i=1;i<=third;i++)
{
if(i%first==0 && i%second==0 )
{
System.out.printf("FB ");
}
else if(i%first==0)
System.out.printf("F ");
else if(i%second==0)
System.out.printf("B " );

else
System.out.printf("%d ",i);

}
System.out.println();
}
{
}
console.close();

}

fizzbuzz java solution

// assuming that the input is provided from the command line with 3 different integers
//first A being fizz
//second B being buzz
//third N being the number of integers to be processed

import java.io.*;
import java.util.*;
public class fizzbuzz {

static Scanner console = new Scanner(System.in);
public static void main(String[] args) throws IOException
{

while(console.hasNext())
{

int first=console.nextInt();
int second =console.nextInt();
int third =console.nextInt();

for(int i=1;i<=third;i++)
{
if(i%first==0 && i%second==0 )
{
System.out.printf("FB");
}

else if(i%first==0)
System.out.printf("F");
else if(i%second==0)
System.out.printf("B" );

else
System.out.printf("%d",i);
}

}



}

}

asp.net using viewstate properties

//C# code
public int intView
        {
            get
            {
                object obj = ViewState["intView"]; //set obj as a the value of intView
                return (obj == null) ? 0 : (int)obj;  // if obj is null return o else return obj which is intView
            }

            set { ViewState["intView"] = value; } // set intView to obj
        }