import java.util.Vector;
public class IntegerCruncher {
  
  /**
   * Precondition: a and b are natural numbers
   * Postcondition: result[0] is the greatest common divisor of a and b &&
   *                result[0] = (a * result[1]) + (b * result[2])
   * 
   * definition: d is the greatest common divisor of a and b if and only if:
   *             d is a natural number that divides both a and b, and
   *             any natural number that divides both a and b also divides d.
   */
  public static int[] MoreEuclid(int a, int b) {
    int[] result= {a,1,0};
    int tmpInt= 0;
    
    if (b != 0) {
      result = MoreEuclid(b, a % b);
      tmpInt= result[1];
      result[1] = result[2];
      result[2] = tmpInt - (result[1] * (a / b));
    }
    
    return result;
  }
  
  /**
   * Precondition: numList is a vector of Integers whose values are natural
   *                   numbers && base is an integer > 1
   * Postcondition: numList contains the same Integers as before, 
   *                  with values in non-decreasing order
  */
  
  public static void baseSort(int base, Vector numList) {
    boolean sorted = false;
    Vector[] digit = new Vector[base];
    
    for (int i = 0; i < base; i++) {
      digit[i] = new Vector();
    }
    
    int magnitude = 1;
    
    while (!sorted) {
      sorted = true;
       
      // sublist by current digit
      for (int i = 0; i < numList.size(); i++) {
        int currentInt = ((Integer) numList.elementAt(i)).intValue();
        int digitIndex = currentInt / magnitude;
        sorted = sorted && digitIndex < base; // or last iteration
        digitIndex %= base;
        digit[digitIndex].add(new Integer(currentInt));
      }
            
      // combine sublists
      numList.clear();
      for (int i = 0; i < base; i++) {
        numList.addAll(digit[i]);
        digit[i].clear();
      }
      
      magnitude *= base;
    } 
  }
 
}