Code Jam 2010: Fair Warning

The problem definition could be found at Code Jam web site.

Official Contest Analysis could be found at Code Jam web site.

My solution is published below.

Main functions:

• public solve - high-level problem solving
• private solve - low -level problem solving

public class FairWarning {
    ...
    private Scanner scanner;
    private PrintWriter writer;
   
    public FairWarning(InputStream is, OutputStream os) {
        scanner = new Scanner(is);
        writer = new PrintWriter(os);
    }
    ...
    /**
     * Solve the problem
     */
    public void solve() {
        int c = scanner.nextInt();
   
        for (int i = 1; i <= c; i++) {
            writer.print("Case #");
            writer.print(i + ": ");
   
            // 2 <= N <= 1000
            int n = scanner.nextInt();
   
            // 1 <= t[i] <= 10^50
            // collect t[i] into a TreeSet to have them sorted
            NavigableSet<BigInteger> t = new TreeSet<BigInteger>();
            for (int j = 0; j < n; j++)
                t.add(new BigInteger(scanner.next()));
   
            writer.println(solve(t));
        }
    }
   
    private BigInteger solve(NavigableSet<BigInteger> t) {
        // find GCD of all differences between
        Iterator i = t.descendingIterator();
        BigInteger prev = null;
        BigInteger div = null;
        while (i.hasNext()) {
            if (prev == null)
                prev = (BigInteger) i.next();
            else {
                BigInteger diff = prev.subtract((BigInteger) i.next()).abs();
                if (diff.equals(BigInteger.ZERO))
                    continue;
                if (div == null)
                    div = diff;
                else
                    div = div.gcd(diff);
            }
        }
   
        // calculate slarboseconds 
        BigInteger mod = prev.mod(div);
        if (mod.equals(BigInteger.ZERO))
            return BigInteger.ZERO;
        return div.subtract(mod);
    }
}

See also other posts in Code Jam