Find the missing number in a array

Question

I'm working on a personal project to practice my programming skills and I came to this problem. I tried to create a program that will find the missing number in a array.

I'm looking forward to upgrading this program and am trying to find the missing numbers in a array. Yes, with an 's'.

/********************************
*A sample program that will solve
*for a missing integer in a given sorted array.
********************************/

public class MissingInteger{

  public static void PrintArray(){
    int []fArrayDuplicate = {1,2,3,4,5,7,8,9,10};
    System.out.println("\nGiven the incomplete array:");
    System.out.print("[");
      for(int a = 0 ; a<fArrayDuplicate.length ; a++)
        System.out.print(" " + fArrayDuplicate[a] + " ");
    System.out.print("]");
    }

  public static void FindMissing(){
    int []finalArray = {1,2,3,4,5,7,8,9,10};
    int len = finalArray.length; //First, I took the length of the array.
    int sum = 0;
      for(int x=0;x<len;x++)
         sum+=finalArray[x]; //Second, I took the sum of the given array.
    int totalNumber = ((len + 1) * (len + 2)) / 2; //Third, I used this formula to get the total number.
    int missingInt = totalNumber - sum; // Fourth, I subtract the sum to total number to get missing integer.
    System.out.println("\nTherefore, the missing integer is " + missingInt + ".");
 }

  public static void main(String[] args){
      PrintArray();
      FindMissing();
    }
}

Answer 1

In Java, the convention wants that methods are written in camelCase. Which means PrintArray should be printArray and so on.

The indentation is a little off with the declaration of the int[]. Instead of this :

int []fArrayDuplicate

It should be like this

int[] fArrayDuplicate

It might look like nitpicking (and it might be!) but it improves readability by a ton.

Talking about nitpicking, I think your for loop could use some spacing :

for(int x=0;x<len;x++)

could be

for (int x = 0; x < len; x++)

When you comment your code, you should explain why you wrote what you did write, not what you wrote. I mean,

int len = finalArray.length; //First, I took the length of the array.

is pretty obvious, so the comment isn't neccessary. I think it is the same for all your comments, except the third. But what I need to understand, as a developper who reads your code, isn't that you used a formula to get the total, but to understand how your formula works so you can get the total.

Both your methods use the same int[], which makes me think it should be a parameter of both your methods, this way you can be sure they will never be different.

public static void main(String[] args){

    int[] fArrayDuplicate = {1,2,3,4,5,7,8,9,10};
    PrintArray(fArrayDuplicate);
    FindMissing(fArrayDuplicate);
}

I also think you should pull out the main method of this class and put it in a class that is used only to start the application with the good parameters. Doing so, you could use your MissingInteger class to only find missing integer. This way, if you ever want to reuse it, you will be able to without bringing the main method with it.

Also, you could make your MissingInteger class respect the OOP more. You could input the int[] in the constructor like so :

public class MissingInteger {

    private int[] fArrayDuplicate;

    public MissingInteger(int[] fArrayDuplicate){

        this.fArrayDuplicate = fArrayDuplicate;
    }

    public void PrintArray(){

        System.out.println("\nGiven the incomplete array:");
        System.out.print("[");
        for(int a = 0 ; a<fArrayDuplicate.length ; a++)
            System.out.print(" " + fArrayDuplicate[a] + " ");
        System.out.print("]");
    }

    public void FindMissing(){

        int len = fArrayDuplicate.length; //First, I took the length of the array.
        int sum = 0;
        for(int x=0;x<len;x++)
            sum+=fArrayDuplicate[x]; //Second, I took the sum of the given array.
        int totalNumber = ((len + 1) * (len + 2)) / 2; //Third, I used this formula to get the total number.
        int missingInt = totalNumber - sum; // Fourth, I subtract the sum to total number to get missing integer.
        System.out.println("\nTherefore, the missing integer is " + missingInt + ".");
    }
}

I think you might want to rename your class to MissingIntegerFinder since well, the class itself isn't about a missing integer, but about finding a missing integer. And the name fArrayDuplicate doesn't mean much to me. There's nothing talking about duplicates in your code, why is it prefixed with a f? I have a hard time to find a better name, someone might find one. But for now I'd name it integersWithOneMissing or... something like that.

Answer 2

I've edited your main a bit to come up with some more variable input.

public static void main(String[] args){
  int[] input = {1,2,3,4,5,6,8,9};
  int[] complete = new int[ input[
                              input.length-1] ]; // Gets the last item of input.length
  for(int i = 0; i < complete.length; i++) // Fills the array with ascending numbers 1-end
      complete[i] = i+1;

  PrintArray(complete);
  FindMissing(input);  
}

The main now makes 2 int-arrays. One is the one you enter manually, the other is generated based on the last number in the given array.

Then I added some arguments to your methods, to pass the arrays through to them.

PrintArray(int[] complete) {
  // Code here
}

FindMissing(int[] input) {
  // Code here
}

This means that fArrayDuplicate and finalArray are thrown out, but that's for the sake of easier editable code.

If you follow those steps, you'll be able to do two things now: use methods with arguments instead of hardcoding data in methods. Also you'll be able to generate an array based on the number last number of the given array.

Right now you're only able to find 1 missing integer, so I have 1 more question/challenge for you, as you wanted to practice your programming: try creating a method public void FindAllMissing(int[] input, int[] complete) that compares them and prints all missing integers.

Answer 3

And here's another dimension to better your algorithm in speed and simplicity:

• XORing two same number results in a Zero.
• Bitwise operation is faster than addition.
• XOR through all elements in the array with all numbers in [1,n] and you will get your result.

Here comes the code:

    int[] arr = {1,3,4};
    int missNum = 0;
    int i;
    // This loop XORs (1^1)^(2)^(3^3)^(4) = 2^4
    for(i=1; i<=arr.length;i++){
        missNum ^= (i^arr[i-1]);
    }
    // This XORs the above result with the last index, i.e. (2^4)^4 = 2.(Eureka!)
    missNum ^= i; //Your sweet little result.