class R{
  // fact
  // Input: integer n >= 0
  // Output: n!
  // Example: 
  //          > fact(6)
  //          720
  public static int fact(int n){
    return n * fact(n-1);
  }
 
  
  // pow 
  // Input: integer x > 0
  //        integer exp >= 0
  // Ouptput: x ^ e
  // Example: 
  //          > R.pow(2,3)
  //          8
  public static int pow(int x, int exp){
    int result = 1;
    for ( ; exp > 0; exp--)
      result *= x;
    return result;
  }
 
  
  // fib
  // Input: a positive integer n 
  // Output: the nth number in the fibonacci series
  // Note: The fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, ...
  //       where fib(n) = fib(n-1) + fib(n-2)
  // Example: 
  //          > R.fib(4)
  //          3
  //          > R.fib(6)
  //          8
  //          > R.fib(10)
  //          55
  public static int fib(int n){
    if (n == 1 || n == 2)
      return 1;
    int num1 = 1;
    int num2 = 1;
    int nextFib = num1 + num2;
    int nextFibIndex = 3;
    while (nextFibIndex < n){
      num1 = num2;
      num2 = nextFib;
      nextFib = num1 + num2;
      nextFibIndex++;
    }
    return nextFib;
  }
  
  
  // sumNums
  // Input: an array of integers
  // Output: sum of integers in array
  // Example: 
  //          > R.sumNums(new int[] {45,55})
  //          100
  public static int sumNums(int[] data){
    int sum = 0;
    for (int i=0; i<data.length; i++)
      sum += data[i];
    return sum;
  }
      

  // binarySearch
  // Input: an array of integers, and an integer key to search for
  // Ouput: the index in the array where key is found; -1 if key not found
  // Example:
  //          > int[] data = {3, 7, 12, 30, 55, 57, 120, 208, 309, 1024};
  //          > R.binarySearch(data, 12)
  //          2
  //          > R.binarySearch(data,1000)
  //          -1
  //          > R.binarySearch(data, 120)
  //          6
  public static int binarySearch(int[] a, int key) {
    int bot = 0, top = a.length;
    while (bot < top) {
      int mid = bot + ((top - bot)/2);
      if (key < a[mid])
        top = mid;
      else if (key > a[mid])
        bot = mid + 1;
      else return mid;
    }
    return -1;
  }
}