Digit Division

import java.util.Arrays;

/**
 * Created by Owner on 2/2/2016.
 */
public class Application {

    public static void main(String[] args) {
        int[] a = new int[] {1, 0, 3, 0, 3, 0, 1};
        int[] b = new int[] {1, 0, 1};
        System.out.println(Arrays.toString(divide(a, b)));
    }

    /****************************/
    /*** Arithmetic Operators ***/
    /****************************/

    /**
     * Divide a by b
     */
    private static int[] divide(int[] a, int[] b) {
        if (isLess(a, b)) {
            return new int[] {0};
        } else if (isEqual(a, b)) {
            return new int[] {1};
        } else {

            int qLength = a.length - b.length + 1;
            int p = b.length - 1;   // So that x is the same length as b
            int[] x = subArray(a, 0, p);
            while (isGreater(b, x)) {
                p++;
                qLength--;
                x = subArray(a, 0, p);
            }
            int[] q = new int[qLength];

            for (int i=0; i<q.length; i++) {
                int c = 1;
                int[] y = multiply(b, c);
                while (isLess(y, x) || isEqual(y, x)) {
                    c++;
                    y = multiply(b, c);
                }
                q[i] = c - 1;
                x = subtract(x, multiply(b, c-1));
                if (p+i+1 < a.length) {
                    x = append(x, a[p+i+1]);
                }
            }

            return q;

        }
    }

    /**
     * Subtract b from a
     */
    private static int[] subtract(int[] a, int[] b) {
        if (isLess(a, b)) {
            return subtract(b, a);
        }
        int[] d = new int[a.length];
        for (int i=0; i<d.length; i++) {
            int ia = a.length - i - 1;
            int ib = b.length - i - 1;
            int id = d.length - i - 1;
            if (ib >= 0) {
                d[id] = a[ia] - b[ib];
            } else {
                d[id] = a[ia];
            }
        }
        return beautify(d, 10);
    }

    /**
     * Multiply a by k
     */
    private static int[] multiply(int[] a, int k) {
        int[] p = new int[a.length];
        for (int i=0; i<p.length; i++) {
            p[i] = a[i]*k;
        }
        return beautify(p, 10);
    }

    /****************************/
    /*** Relational Operators ***/
    /****************************/

    /**
     * Tells you if a is equal to b
     */
    private static boolean isEqual(int[] a, int[] b) {
        if (a.length != b.length) {
            return false;
        } else {
            for (int i=0; i<a.length; i++) {
                if (a[i] != b[i]) {
                    return false;
                }
            }
            return true;
        }
    }

    /**
     * Tells you if a is less than b
     */
    private static boolean isLess(int[] a, int[] b) {
        if (a.length < b.length) {
            return true;
        } else if (a.length > b.length) {
            return false;
        } else {
            for (int i=0; i<a.length; i++) {
                if (a[i] < b[i]) {
                    return true;
                } else if (a[i] > b[i]) {
                    return false;
                }
            }
            return false;
        }
    }

    /**
     * Tells you if a is greater than b
     */
    private static boolean isGreater(int[] a, int[] b) {
        if (a.length > b.length) {
            return true;
        } else if (a.length < b.length) {
            return false;
        } else {
            for (int i=0; i<a.length; i++) {
                if (a[i] > b[i]) {
                    return true;
                } else if (a[i] < b[i]) {
                    return false;
                }
            }
            return false;
        }
    }

    /******************/
    /*** Formatting ***/
    /******************/

    /**
     * Ensure that all digits of a are within
     * the range [0, b). Remove all leading zeros.
     *
     * @param b
     *          The base of the number a
     */
    private static int[] beautify(int[] a, int b) {
        a = propagateDigits(a, b);
        return removeLeadingZeros(a);
    }

    /**
     * Ensure that all digits of a
     * are within the range [0, b)
     *
     * @param b
     *          The base of the number a
     */
    private static int[] propagateDigits(int[] a, int b) {
        int[] c = copy(a);
        for (int i=c.length-1; i>=0; i--) {
            if (c[i] >= b) {
                int overflow = c[i] / b;
                if (i > 0) {
                    c[i-1] += overflow;
                } else {
                    c = prepend(c, overflow);
                    i++;
                }
                c[i] = c[i] % b;
            } else if (c[i] < 0) {
                if (i > 0) {
                    int borrow = -((int) Math.floor(((float) c[i]) / b));
                    c[i-1] -= borrow;
                    c[i] += (borrow * b);
                }
            }
        }
        return c;
    }

    /**
     * Remove all leading zeros of a
     */
    private static int[] removeLeadingZeros(int[] a) {
        int actualLength = 0;
        for (int i=0; i<a.length; i++) {
            if (a[i] != 0) {
                actualLength = a.length - i;
                break;
            }
        }
        int[] r = new int[actualLength];
        for (int i=0; i<r.length; i++) {
            r[r.length-i-1] = a[a.length-i-1];
        }
        return r;
    }

    /***********************/
    /*** Array Utilities ***/
    /***********************/

    /**
     * Creates a copy of an array
     */
    private static int[] copy(int[] a) {
        int[] b = new int[a.length];
        for (int i=0; i<a.length; i++) {
            b[i] = a[i];
        }
        return b;
    }

    /**
     * Add b to the beginning of a
     */
    private static int[] prepend(int[] a, int b) {
        int[] r = new int[a.length+1];
        r[0] = b;
        for (int i=0; i<a.length; i++) {
            r[i+1] = a[i];
        }
        return r;
    }

    /**
     * Add b to the end of a
     */
    private static int[] append(int[] a, int b) {
        int[] r = new int[a.length+1];
        for (int i=0; i<a.length; i++) {
            r[i] = a[i];
        }
        r[r.length-1] = b;
        return r;
    }

    /**
     * Return sub-array of a from a[start] to a[end], inclusive
     */
    private static int[] subArray(int[] a, int start, int end) {
        int[] s = new int[end - start + 1];
        for (int i=0; i<s.length; i++) {
            s[i] = a[start+i];
        }
        return s;
    }

}