Find missing numbers in a range, with duplicate numbers in a sorted array

Question

Suggestions for cleanup and optimization request.

This question is a follow-up question on this post.

Lets assume the range of

1, 2, 3, 4.

This function takes in an array of repeated elements, [1,1,4,4] and the output is [2, 3].

The question marked as duplicate takes an input of [1, 4] and output is [2, 3]. While output is same, the input differs. Please make a note of this difference between two questions causing confusion.

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

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

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }

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


    public final class FindMissingRepeating {

        /**
         * Takes an input a sorted array with only two variables that repeat once. in the
         * range. and returns two variables that are  missing.
         * 
         * If any of the above condition does not hold true at input the results are unpredictable.
         * 
         * Example of input:
         * range: 1, 2, 3, 4
         * input array [1, 1, 4, 4]
         * the variables should contain 2 missing elements ie 2 and 3
         * 
         * @param a : the sorted array.
         */
        public static Variables sortedConsecutiveTwoRepeating (int[] a, int startOfRange) {
            if (a == null) throw new NullPointerException("a1 cannot be null. ");

            int low = startOfRange;
            int high = low + (a.length - 1);

            int x = 0;
            int i = 0;
            boolean foundX = false;

            while  (i < a.length) {
                if (a[i] < low) {
                    i++;
                } else {
                    if (a[i] > low) {
                        if (foundX) {
                            return new Variables(x, low);
                        } else {
                            x = low;
                            foundX = true;
                        }
                    }
                    low++;
                    i++;
                } 
            }

            int val = foundX ? x : high - 1;
            return new Variables(val, high);
         }



        public static void main(String[] args) {
            int[] ar1 = {1, 2, 2, 3, 4, 4, 5};
            Variables v1 = FindMissingRepeating.sortedConsecutiveTwoRepeating (ar1, 1);
            System.out.println("Expected x = 6, y = 7 " + v1);

            int[] ar2 = {2, 2, 4, 4, 5, 6, 7};
            Variables v2 = FindMissingRepeating.sortedConsecutiveTwoRepeating (ar2, 1);
            System.out.println("Expected x = 1, y = 3 " + v2);

            int[] ar3 = {3, 3, 4, 4, 5, 6, 7};
            Variables v3 = FindMissingRepeating.sortedConsecutiveTwoRepeating (ar3, 1);
            System.out.println("Expected x = 1, y = 2 " + v3);

            int[] ar4 = {1, 3, 3, 4, 4, 6, 7};
            Variables v4 = FindMissingRepeating.sortedConsecutiveTwoRepeating (ar4, 1);
            System.out.println("Expected x = 2, y = 5 " + v4);
        }
    }

Answer 1

Firstly there are 2 classes so don't show them as a single code when showing your code. Place a heading with the class name then your code then second class name then your second class's code. That makes it easier to copy paste it into Eclipse when seeing the code.

Why have you named the parameters as x2 and y2 and still using the this keyword? Why are you making the variable names different in the first place? It just adds confusion. Name them as x and y and then use the this keyword. Period.

You are throwing a null pointer exception when a is null and the message is a1 is null. That will become confusing... Also you don't need to throw that explicitly. The assignment to high will throw the exception and give you a proper stacktrace already without any extra code.

The while loop can be made a for loop very easily and will limit the scope and extra variable (i in this case). Note that you are doing i++ in both if as well as else. That shows you didn't take the time to look at your own code.

You passed startOfRange to the function and forgot that it is a variable also. If you have any intention of not changing it then make it explicit and declare the parameter as final in the method's signature.

Also If I am correct then you have used x = 0 only to make it one less than the startRange so that your algorithm works. That means your function will break the moment you decide the startRange to be anything other than 1. Also using such magic numbers and such variable names as x is a bad idea. Really bad idea.

Take some time to refactor the code yourself. It pays if your code is easy to understand by other programmers. Your code can be changed to this and I think now it is much easier to understand the flow of execution of the current program.

public static ExVariables sortedConsecutiveTwoRepeating(int[] a,
        final int startOfRange) {

    int low = startOfRange;
    int high = low + (a.length - 1);

    int x = low - 1;
    boolean foundX = false;

    for (int i = 0; i < a.length; i++) {
        if (a[i] > low) {
            if (foundX) {
                return new ExVariables(x, low);
            }
            x = low;
            foundX = true;
        }
        if (a[i] >= low) {
            low++;
        }
    }

    if (foundX) {
        return new ExVariables(x, high);
    } else {
        return new ExVariables(high - 1, high);
    }
}

I think it should be possible to refactor it more so that the return comes only inside the for loop but I didn't take the time to do that.

Hope this helps.