Quickest way to find missing number in an array of numbers

by

You can do this in O(n). Iterate through the array and compute the sum of all numbers. Now, sum of natural numbers from 1 to N, can be expressed as Nx(N+1)/2. In your case N=100.

Subtract the sum of the array from Nx(N+1)/2, where N=100.

That is the missing number. The empty slot can be detected during the iteration in which the sum is computed.

// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
    if (arr[i] == 0)
    {
         idx = i; 
    }
    else 
    {
         sum += arr[i];
    }
}

// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is: " + (total - sum) + " at index " + idx);

More Related Contents:

  1. How to remove repetition in output results in this code
  2. Write a program that takes an array/arraylist of integer and finds longest sub array/arraylist whose entries are equal [closed]
  3. Finding the max/min value in an array of primitives using Java
  4. Connect 4 check for a win algorithm
  5. Finding the second highest number in array
  6. Java, find intersection of two arrays
  7. Java, Shifting Elements in an Array
  8. Find duplicate element in array in time O(n)
  9. All possible combinations of an array
  10. Flatten nested arrays in java
  11. How to find the only number in an array that doesn’t occur twice [duplicate]
  12. Generate Random Numbers in Array [duplicate]
  13. find an element in a sorted matrix [duplicate]
  14. Interview question – Search in sorted array X for index i such that X[i] = i
  15. Write a function that will sort a string array using Java
  16. Algorithm to divide a given number in two proportions by one of the component of that number
  17. Convert list to array in Java [duplicate]
  18. Converting array to list in Java
  19. Accessing members of items in a JSONArray with Java
  20. How to sort an array of objects in Java?
  21. Problem with assigning an array to other array in Java
  22. Why does Collections.sort use Mergesort but Arrays.sort does not?
  23. Why is System.arraycopy native in Java?
  24. Java Arrays.equals() returns false for two dimensional arrays
  25. How to convert JSONObjects to JSONArray?
  26. java – passing array in oracle stored procedure
  27. Nice Label Algorithm for Charts with minimum ticks
  28. Hash Set and Array List performances
  29. how calculate java array memory usage
  30. Why are new java.util.Arrays methods in Java 8 not overloaded for all the primitive types?

Leave a Comment