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();
 }
}

• Friso van Dijk: So you want to enter any number-array and check for missing numbers? Assuming they are 1-x ascending?
• Yodism: In this program I put the missing number constantly(which is 6) but i'm still working with an input to determine the missing number.
• user2023861: If the array always starts at one, and each successive element is always supposed to be one higher than the previous, why not just compare fArrayDuplicate[i] to fArrayDuplicate[i + 1]. If the difference is two, then one number is missing. If the difference is three, then two numbers are missing, etc. This works on a sorted array. Your algorithm works on both sorted and unsorted arrays, but it's more complicated than what I described for sorted arrays.
• user2023861: Also, since you want your algorithm to support multiple unknowns, you need multiple equations. If two numbers are missing, you need two equations, i.e, sum(1 to n) = Sum(array) + m1 + m2 and sumOfSquares(1 to n) = SumOfSquares(array) + m1^2 + m2 ^ 2. Solve for m1 and m2. As the number of missing numbers increases, this approach becomes untenable. I'd recommend an in-place bucket sort. This runs in linear time (even though it's a sorting-algorithm) and requires only one pass through the array.
• Abr001am: you can do a hash function , then the indexes of all empty cells in hash array are representing missing values , keep an eye to not fall into a hash collision

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.

• Yodism: Wow. Thank you very much sir. After I read your comments I realized so many things about my code. I almost think earlier that my code is already clean but it's not. Thanks for the advise as a student. :)
• IEatBagels: It is a pleasure. Your code isn't wrong, there are some improvements possible!

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.

• IEatBagels: Your code doesn't give the same result as the OP's one. The complete array would contain {1,2,3,4,5,6,7,8,9} and OP's array contains {1,2,3,4,5,7,8,9}.
• IEatBagels: But your answer does follow CR's standards, keep it this way!
• Friso van Dijk: Ah yeah, my bad. I thought he printed the complete array.

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.