Find a missing numbers, single missing number and two missing numbers, from consecutive range

Question

Contains 3 options. Given an input array

1. Unsorted and consecutive range, and array is 1 element short. eg: range is 6-9, and array = [7, 8, 9] output should be 6.
2. All conditions same as previous except 2 numbers are missing.
3. Input is sorted, numbers are consecutive, array has one missing element.

Code:

final class Variables {
    private final double x;
    private final double y;

    Variables(double x2, double y2) {
        this.x = x2;
        this.y = y2;
    }

    public double getX() {
        return x;
    }

    public double getY() {
        return y;
    }

    @Override public String toString()  { 
        return "x = " + x + " y = " + y;
    }
}

public final class FindMissing {

    private FindMissing() {};

    /**
     * The input array must contain only 1 element lesser than range.
     * Returns a missing element.
     */
    public static final int unsortedConsecutiveSingleMissing(int[] a1, int low, int high) {
        // check that array length should be only 1 element less - can be avoided due to its mention in javadoc
        if (a1 == null) throw new NullPointerException("a1 cannot be null. ");
        if (low >= high) throw new IllegalArgumentException("The low: " + low + " should be lesser than high: " + high);

        int total = (high * (high + 1)/2) - (low * (low + 1)/2) + low;

        for (int i = 0; i < a1.length; i++) {
            total = total - a1[i];
        }
        return total;
    }


    /**
     * The input array must contain only 2 element lesser than range.
     * Returns a missing element.
     * 
     * Consecutive numbers are present, array is unsorted and a single number repeats.
     * 
     * (a + b)2 = a2 + b2 + 2ab
     * 
     * a  + b  = S' - S''
     * a2 + b2 = T' - T''
     * 
     * S' & S'' : sum of first and second sequence accordingly.
     * T' & T'' : sum square of each number in T' and T'' accordingly.
     */
    public static final Variables unsortedConsecutiveTwoMissing(int[] a1, int low, int high) {
        if (a1 == null) throw new NullPointerException("a1 cannot be null. ");
        if (low >= high) throw new IllegalArgumentException("The low: " + low + " should be lesser than high: " + high);

        int sum1 = 0;
        int squareSum1 = 0;
        int x = low;
        // careful. we need to be <= not <. due to muscle memory it is easy to be careless here.
        while (x <= high) {
            sum1 = sum1 + x;
            squareSum1 = squareSum1 + x * x;
            x++;
        }

        int sum2 = 0;
        int squareSum2 = 0;
        for (int i = 0; i < a1.length; i++) {
            sum2 = sum2 + a1[i];
            squareSum2 = squareSum2 + a1[i] * a1[i];
        }

        int sumDiff = sum1 - sum2;

        int squareDiff = squareSum1 - squareSum2;
        // (x + y)2 = x2 + y2 + 2xy
        int product = ((sumDiff * sumDiff) - squareDiff) / 2;

        return getVariables(product, sumDiff);
    }

    private static Variables getVariables(double product, double sum) {
        // using reduced quadratic equation.
        double x =  (sum/2) - Math.sqrt( ((sum/2) * (sum/2)) - product);
        double y = sum - x;
        return new Variables(x, y);
    }    



    /**
     * 
     * The input array must be sorted and must contain only 1 element lesser than range.
     * Returns a missing element.
     */
    public static Integer sortedConsecutiveSingleMissing(int[] a1, int low) {
        if (a1 == null) throw new NullPointerException("a1 cannot be null. ");

        int start  = a1[0];
        if (start != low) {
            return low;
        }
        int last = a1[a1.length - 1];
        if (last != a1.length + low) {
            return last + 1;
        }

        int lb = 0;
        int hb = a1.length - 1;

        while (lb <= hb) {
            int mid =  (lb + hb) / 2;

            if (a1[mid] + 1 != a1[mid + 1]) {
                return a1[mid] + 1;
            }
            if ((a1[mid] - mid) > start) {
                hb = mid - 1;
            } else {
                lb = mid + 1;
            }
        }
        return null;
    }

}

Answer 1

My comments related to unsortedConsecutiveSingleMissing:

1. The calculation of total using the formula int total = (high * (high + 1)/2) - (low * (low + 1)/2) + low;:

   • is susceptible to integer overflow issues (Consider when high is really high and low is still positive).
   • is doing a lot of extra work to evaluate an Arithmetic Progression. Unfortunately, you are using the formula to sum first n natural numbers twice to get this result. You can use the much more straightforward formula n*(a+l)/2 where:
     • a is the first term (low in your code);
     • l is the last term (high); and
     • n is the number of terms in the AP (high - low + 1)

2. This calculation of total, irrespective of the process used, is susceptible to overflow. The algorithm used needs to be adapted to avoid calculating the total at all. (There is a way to do that and still keep the code O(1) in space and O(n) in time.)

My comments related to unsortedConsecutiveTwoMissing:

1. You could have used the formulae to calculate the sum of the sequence and sum of the squared sequence. Again, whatever you use is susceptible to overflow. If you have acknowledged the review comment for the above method, you can remove the problem here as well. (Hint: It'll also reduce your two loops to calculate the sum1 and sum2 into a single loop.)
2. Even after solving the problem with the calculation of the sum and the squared sum, your calculation of product can overflow once again. In fact it's unavoidable in your algorithm. Consider the case when the missing numbers are Integer.MAX_VALUE and Integer.MAX_VALUE - 1, the product is -2147483646 while the sum is -3. The solution is pretty difficult to obtain now.
3. Needless to say, you need to change your algorithm once again.
4. Return an object containing integers not doubles. The problem states that the sequence is missing integers.

getVariables() suffers from the same problems. So, I won't be adding any comments separately.

Answer 2

1. I'd suggest some naming improvements for your variables:
   • a1 -> numbers or sequence
   • sum1/squareSum1 -> sumRange/squareSumRange
   • sum2/squareSum2 -> sumNumbers or sumSequence / squareSumNumbers
2. In the comments to unsortedConsecutiveTwoMissing you state: (a + b)2 = a2 + b2 + 2ab which is not immediately visible that this means the binomic formula. The text representation for power of is typically ^ which would mean the comment should look like this: (a + b)^2 = a^2 + b^2 + 2ab

3. While the binary search in sortedConsecutiveSingleMissing is O(log(n)) in production code I'd consider using the same solution as for unsortedConsecutiveSingleMissing. While this is O(n) it has some advantages

   • It's a simpler solution (easier to understand and maintain, less bugs to write)
   • Use one single proven solution (share the code)
   • Less code to write and maintain (means less bugs)

   Only if it would prove to be a performance problem I'd go down a more complicated path.