15-100 Sections S-V
Fall 2008 / Midterm Exam #1 (Programming Portion)
Exam Date:  Fri 10-Oct-2008

2 Questions / 40 Minutes (Actual Time on Task)

BEFORE starting:  Read these instructions first!

  1. Do EITHER ONE (your choice) but NOT BOTH of these:
     
    1. nthPowerfulNumber
      A "powerful" number is a positive integer m that for every prime number p dividing m, p2 also divides m. So 12 is not powerful because 3 divides 12 but 32=9 does not divide 12.  We assume 1 is powerful (because no prime numbers divide it). Here are the first several powerful numbers:
           1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, 108, ...
      Write the following method:
        public static int nthPowerfulNumber(int n)
      This method takes a number n and returns the nth powerful number, or -1 if n is non-positive.  Here is a test method:
        public static void testNthPowerfulNumber() {
    System.out.print("Testing nthPowerfulNumber... ");
    Assert(nthPowerfulNumber(-1) == -1);
    Assert(nthPowerfulNumber(0) == -1);
    Assert(nthPowerfulNumber(1) == 1);
    Assert(nthPowerfulNumber(2) == 4);
    Assert(nthPowerfulNumber(3) == 8);
    Assert(nthPowerfulNumber(12) == 72);
    Assert(nthPowerfulNumber(50) == 900);
    System.out.println("Passed all tests!");
  }
    2. nthOddishNumber
      We will say that a number is "oddish" (our term) if it is positive and it has more odd digits than even digits. So, 91234 is oddish because it has 3 odd digits and 2 even digits, and 76 is not oddish because it does not have more odd digits than even digits.  Here are the first several oddish numbers:
         1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 31, 33, 35, 37, 39, 51, ...
      Write the following method:
        public static int nthOddishNumber(int n)
      This method takes a number n and returns the nth oddish number, or -1 if n is non-positive. Here is a test method:
        public static void testNthOddishNumber() {
    System.out.print("Testing nthOddishNumber... ");
    Assert(nthOddishNumber(-1) == -1);
    Assert(nthOddishNumber(0) == -1);
    Assert(nthOddishNumber(1) == 1);
    Assert(nthOddishNumber(2) == 3);
    Assert(nthOddishNumber(3) == 5);
    Assert(nthOddishNumber(11) == 31);
    Assert(nthOddishNumber(1234) == 3217);
    System.out.println("Passed all tests!");
  }
  2. Do EITHER ONE (your choice) but NOT BOTH of these:
     
    1. medianLength
      Write the following method:
        public static int medianLength(String[] a)
      This method returns the median length of the Strings in the given array, or -1 if the array is either empty or null.  Note that the median of an odd list is the middle element, and the median of an even list is the average of the middle two elements..  Here is a test method:
        public static void testMedianLength() {
    System.out.print("Testing medianLength... ");
    Assert(medianLength(null) == -1);
    String[] a0 = { };
    Assert(medianLength(a0) == -1);
    String[] a1 = { "this", "is", "a", "test" };
    Assert(medianLength(a1) == 3);
    String[] a2 = { "this", "is", "another", "test" };
    Assert(medianLength(a2) == 4);
    String[] a3 = { "12345", "1234", "1234567"};
    Assert(medianLength(a3) == 5);
    System.out.println("Passed all tests!");
  }
    2. hasDuplicate
      Write the following method:
        public static boolean hasDuplicate(String[] a)
      This method returns true if at least one string occurs at least twice in the given array, and false otherwise (including if the array is null)..  Here is a test method:
        public static void testHasDuplicate() {
    System.out.print("Testing hasDuplicate... ");
    Assert(hasDuplicate(null) == false);
    String[] a1 = { "no", "No", "NO!!!" };
    Assert(hasDuplicate(a1) == false);
    String[] a2 = { "aaaa" };
    Assert(hasDuplicate(a2) == false);
    String[] a3 = { "this", "is", "a", "test", "it", "is" };
    Assert(hasDuplicate(a3) == true);
    System.out.println("Passed all tests!");
  }
  3. Bonus/Optional:  isHappy
    A happy number is defined by the following process:  Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.  Those numbers for which this process ends in 1 are happy numbers, while those that do not end in 1 are unhappy numbers.  Write the following method:
      public static boolean isHappy(int n)
    This method takes an integer and returns true if it is a happy number and false otherwise. Note that non-positive numbers are not happy.  HINT:  Interestingly, every number that ends in a cycle ends in the SAME cycle. You will probably need this hint to solve this problem.  Here is a test method:
      public static void testIsHappy() {
    System.out.print("Testing isHappy... ");
    Assert(isHappy(-1) == false);
    Assert(isHappy(0) == false);
    Assert(isHappy(1) == true);
    Assert(isHappy(10) == true);
    Assert(isHappy(12) == false);
    Assert(isHappy(13) == true);
    Assert(isHappy(495) == false);
    Assert(isHappy(496) == true);
    System.out.println("Passed all tests!");
  }

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem