// Solutions to Test 2 Review 1 CompSci 6 Spring 2005


//------------------------------------------------------------
// Question 1
//

boolean isValid (String ccard)
{ 
    int total = 0;

    for (int k = 0; k < s.length(); k++)
    {
        int digit = Integer.parseInt(s.substring(k, k+1));
        if (k % 2 != 0)
        {
            digit *= 2;
            if (digit >= 10)
            {
                digit -= 9;
            }
        }
        total += digit;
    }

    return (total % 10 == 0);
}


//------------------------------------------------------------
// Question 2
//

// Part A
// The flaw in the code is that results represents the empty set
// (i.e., it contains no items) since it is created but nothing 
// is added to it.  The intersection of the empty set with any
// other set is still the empty set (i.e., any items have nothing
// in common with no items).

// Part B
// The solution is to add all the items from one the given sets 
// to results, so it starts as something other than the empty set.


//------------------------------------------------------------
// Question 3
//

// Part A
public boolean isAcsending (List<Comparable> data)
{
    for (int k = 1; k < data.size(); k++)
    {
        Comparable previous = data.get(k - 1);
        Comparable current = data.get(k);
        if (previous.compareTo(current) < 0)
        {
            return false;
        }
    }

    return true;
}

// Part B
public int minInARow (List<Object> values, Object toFind)
{
    int min = values.size();
    int numInARow = 0;

    for (Object current : values)
    {
        if (current.equals(toFind))
        {
            numInARow++;
        }
        else
        {
            if (numInARow > 0 && numInARow < min)
            {
                min = numInARow;
            }
            numInARow = 0;
        }
    }

    if (min == values.size()) return 0;
    else                      return min;
}



//------------------------------------------------------------
// Question 4
//

// Part A
public int findDupe (int[] data)
{
    int[] counts = new int[data.length];
    Arrays.fill(counts, 0);
    
    // for each number in data, count how many times it appears
    for (int k = 0; k < data.length; k++)
    {
        int value = data[k];
        int count = counts[value];
     
        // return number appearing more than once
        if (count > 0)
        {
            return value;
        }
        else
        {
            counts[value]++;
        }
    }
}


// Part B
// Since the numbers range from 1 to count - 1 inclusive and only 
// one is repeated, it is guaranteed that each number within that 
// range is represented.  This leads to the following psuedocode:
//
//   int simpleTotal = 0;
//   int dataTotal   = 0;
//
//   for (int k = 0; k < data.size(); k++)
//   {
//       simpleTotal += k;
//       dataTotal   += data[k];
//   }
//
//   return dataTotal - simpleTotal;