The fastest way to find the missing number in an array of numbers

Question

I have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. Numbers are randomly added to the array, but there is one random empty slot in the array. What is the fastest way to find this slot, as well as the number to put in the slot? Preferred is a Java solution.

Answer 1

You can do it in O (n). We pass through the array and calculate the sum of all numbers. Now the 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.

This is the missing number. An empty slot can be detected during the iteration in which the sum is calculated.

 // 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); 

Answer 2

 long n = 100; int a[] = new int[n]; //XOR of all numbers from 1 to n // n%4 == 0 ---> n // n%4 == 1 ---> 1 // n%4 == 2 ---> n + 1 // n%4 == 3 ---> 0 long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0; for (long i = 1; i <= n; i++) { xor = xor ^ a[i]; } //Missing number System.out.println(xor); 

Answer 3

We can use the XOR operation, which is safer than the summation, because in programming languages, if the given input is large, it can overflow and may give the wrong answer.

Before proceeding to the solution, be aware that A xor A = 0 . Therefore, if we have XOR two identical numbers, the value is 0.

Now XORing [1..n] with elements present in the array cancels the same numbers. Therefore, in the end we get the missing number.

 // Assuming that the array contains 99 distinct integers between 1..99 // and empty slot value is zero int XOR = 0; for(int i=0; i<100; i++) { if (ARRAY[i] != 0) XOR ^= ARRAY[i]; XOR ^= (i + 1); } return XOR; 

Answer 4

It was an interview question with Amazon, and the answer was initially given: We have numbers from 1 to 52 that fit into an array of numbers 51, what's the best way to find out which number is missing?

This was answered as shown below:

 1) Calculate the sum of all numbers stored in the array of size 51. 2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2. 

Here were also presented blogs: Working with software - a question about yourself

Answer 5

Here is a simple program to find the missing numbers in an integer array

 ArrayList<Integer> arr = new ArrayList<Integer>(); int a[] = { 1,3,4,5,6,7,10 }; int j = a[0]; for (int i=0;i<a.length;i++) { if (j==a[i]) { j++; continue; } else { arr.add(j); i--; j++; } } System.out.println("missing numbers are "); for(int r : arr) { System.out.println(" " + r); } 

Answer 6

5050 - (sum of all values ​​in the array) = missing number

 int sum = 0; int idx = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) idx = i; else sum += arr[i]; } System.out.println("missing number is: " + (5050 - sum) + " at index " + idx); 

Answer 7

This is C #, but it should be close to what you need:

 int sumNumbers = 0; int emptySlotIndex = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) emptySlotIndex = i; sumNumbers += arr[i]; } int missingNumber = 5050 - sumNumbers; 

Answer 8

Well, use a flowering filter.

 int findmissing(int arr[], int n) { long bloom=0; int i; for(i=0; i<;n; i++)bloom+=1>>arr[i]; for(i=1; i<=n, (bloom<<i & 1); i++); return i; } 

Answer 9

In a similar scenario where the array is already sorted , it does not include duplicates and only one number is missing , you can find this missing number in the log (n) time using binary search.

 public static int getMissingInt(int[] intArray, int left, int right) { if (right == left + 1) return intArray[right] - 1; int pivot = left + (right - left) / 2; if (intArray[pivot] == intArray[left] + (intArray[right] - intArray[left]) / 2 - (right - left) % 2) return getMissingInt(intArray, pivot, right); else return getMissingInt(intArray, left, pivot); } public static void main(String args[]) { int[] array = new int[]{3, 4, 5, 6, 7, 8, 10}; int missingInt = getMissingInt(array, 0, array.length-1); System.out.println(missingInt); //it prints 9 } 

Answer 10

A solution that does not include repetitive additions or maybe the formula n (n + 1) / 2 does not get you for an interview, for example.

You should use an array of 4 integers (32 bits) or 2 int (64 bits). Initialize the last int with (-1 and ~ (1 <31)) → 3. (bits that exceed 100 are set to 1). Or you can set bits above 100 using a for loop.

• Go through the array of numbers and set 1 for the bit position corresponding to the number (for example, 71 will be set to the third int on the 7th bit from left to right)
• Pass through an array of 4 ints (32-bit) or 2 ints (64-bit)

 public int MissingNumber(int a[]) { int bits = sizeof(int) * 8; int i = 0; int no = 0; while(a[i] == -1)//this means a[i] bits are all set to 1, the numbers is not inside this 32 numbers section { no += bits; i++; } return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something) }
public int MissingNumber(int a[]) { int bits = sizeof(int) * 8; int i = 0; int no = 0; while(a[i] == -1)//this means a[i] bits are all set to 1, the numbers is not inside this 32 numbers section { no += bits; i++; } return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something) } 

Example: (32-bit version) allows you to say that the missing number is 58. This means that the 26th bit (from left to right) of the second integer is 0.

The first int is -1 (all bits are set), so we go to the second and add the number “no” 32. The second int is different from -1 (the bit is not set), therefore, applying the NOT (~) operator to the number we get 64. The possible numbers are 2 for power x, and we can calculate x using log based on 2; in this case we get log2 (64) = 6 => 32 + 32 - 6 = 58.

Hope this helps.

Answer 11

This is not a search issue. The employer wonders if you have a grip on the checksum. You may need a binary or loop or something else if you are looking for a few unique integers, but the question involves "one random empty slot." In this case, we can use the sum of the stream. Condition: "Numbers accidentally added to the array" are meaningless without additional details. The question does not suggest that the array should begin with an integer 1 and, thus, endure it with an integer at the beginning of the offset.

 int[] test = {2,3,4,5,6,7,8,9,10, 12,13,14 }; /*get the missing integer*/ int max = test[test.length - 1]; int min = test[0]; int sum = Arrays.stream(test).sum(); int actual = (((max*(max+1))/2)-min+1); //Find: //the missing value System.out.println(actual - sum); //the slot System.out.println(actual - sum - min); 

Success Time: 0.18 Memory: 320576 Signal: 0

Answer 12

I found this beautiful solution here:

http://javaconceptoftheday.com/java-puzzle-interview-program-find-missing-number-in-an-array/

 public class MissingNumberInArray { //Method to calculate sum of 'n' numbers static int sumOfNnumbers(int n) { int sum = (n * (n+1))/ 2; return sum; } //Method to calculate sum of all elements of array static int sumOfElements(int[] array) { int sum = 0; for (int i = 0; i < array.length; i++) { sum = sum + array[i]; } return sum; } public static void main(String[] args) { int n = 8; int[] a = {1, 4, 5, 3, 7, 8, 6}; //Step 1 int sumOfNnumbers = sumOfNnumbers(n); //Step 2 int sumOfElements = sumOfElements(a); //Step 3 int missingNumber = sumOfNnumbers - sumOfElements; System.out.println("Missing Number is = "+missingNumber); } } 

Answer 13

======== The simplest solution for a sorted array ============

 public int getMissingNumber(int[] sortedArray) { int missingNumber = 0; int missingNumberIndex=0; for (int i = 0; i < sortedArray.length; i++) { if (sortedArray[i] == 0) { missingNumber = (sortedArray[i + 1]) - 1; missingNumberIndex=i; System.out.println("missingNumberIndex: "+missingNumberIndex); break; } } return missingNumber; } 

Answer 14

Search for a missing number from a series of numbers. IMP indicates to remember.

• the array must be sorted.
• The function does not work with several missed messages.

• the sequence must be an access point.

    public int execute2(int[] array) { int diff = Math.min(array[1]-array[0], array[2]-array[1]); int min = 0, max = arr.length-1; boolean missingNum = true; while(min<max) { int mid = (min + max) >>> 1; int leftDiff = array[mid] - array[min]; if(leftDiff > diff * (mid - min)) { if(mid-min == 1) return (array[mid] + array[min])/2; max = mid; missingNum = false; continue; } int rightDiff = array[max] - array[mid]; if(rightDiff > diff * (max - mid)) { if(max-mid == 1) return (array[max] + array[mid])/2; min = mid; missingNum = false; continue; } if(missingNum) break; } return -1; } 

Answer 15

I think that the simplest and possibly the most effective solution would be to sort through all the records and use the bitrate to remember which numbers are set, and then check for 0 bits. A write with 0 bits is the missing number.

Answer 16

This program finds the missing numbers

 <?php $arr_num=array("1","2","3","5","6"); $n=count($arr_num); for($i=1;$i<=$n;$i++) { if(!in_array($i,$arr_num)) { array_push($arr_num,$i);print_r($arr_num);exit; } } ?> 

Answer 17

One thing you can do is sort the numbers using, for example, quick sort. Then use the for loop to iterate through the sorted array from 1 to 100. At each iteration, you compare the number in the array with your increment for the loop, if you find that the index increment does not match the array value, you find the missing number as well as the missing index .

Answer 18

Below is a solution for finding all the missing numbers from a given array:

 public class FindMissingNumbers { /** * The function prints all the missing numbers from "n" consecutive numbers. * The number of missing numbers is not given and all the numbers in the * given array are assumed to be unique. * * A similar approach can be used to find all no-unique/ unique numbers from * the given array * * @param n * total count of numbers in the sequence * @param numbers * is an unsorted array of all the numbers from 1 - n with some * numbers missing. * */ public static void findMissingNumbers(int n, int[] numbers) { if (n < 1) { return; } byte[] bytes = new byte[n / 8]; int countOfMissingNumbers = n - numbers.length; if (countOfMissingNumbers == 0) { return; } for (int currentNumber : numbers) { int byteIndex = (currentNumber - 1) / 8; int bit = (currentNumber - byteIndex * 8) - 1; // Update the "bit" in bytes[byteIndex] int mask = 1 << bit; bytes[byteIndex] |= mask; } for (int index = 0; index < bytes.length - 2; index++) { if (bytes[index] != -128) { for (int i = 0; i < 8; i++) { if ((bytes[index] >> i & 1) == 0) { System.out.println("Missing number: " + ((index * 8) + i + 1)); } } } } // Last byte int loopTill = n % 8 == 0 ? 8 : n % 8; for (int index = 0; index < loopTill; index++) { if ((bytes[bytes.length - 1] >> index & 1) == 0) { System.out.println("Missing number: " + (((bytes.length - 1) * 8) + index + 1)); } } } public static void main(String[] args) { List<Integer> arrayList = new ArrayList<Integer>(); int n = 128; int m = 5; for (int i = 1; i <= n; i++) { arrayList.add(i); } Collections.shuffle(arrayList); for (int i = 1; i <= 5; i++) { System.out.println("Removing:" + arrayList.remove(i)); } int[] array = new int[n - m]; for (int i = 0; i < (n - m); i++) { array[i] = arrayList.get(i); } System.out.println("Array is: " + Arrays.toString(array)); findMissingNumbers(n, array); } } 

Answer 19

Suppose you have n equal to 8, and our numbers range from 0 to 8 for this example, we can present a binary representation of all 9 numbers as follows 0000 0001 0010 0011 0100 0101 0110 0111 1000

in the above sequence there are no missing numbers, and in each column the number of matches and matches coincides, however, as soon as you delete 1 value, say 3, we get a balance of 0 and 1 columns, If the number 0 in the column is <= number 1, our missing number will have 0 at this bit position, otherwise, if the number 0> number 1 at this bit position, then this bit position will be 1. We test the bit from left to right, and at each iteration we throw half the array for testing the next bit or odd array values, or even array values ​​are discarded at each iteration, depending on which bit we are flawed.

The solution below is in C ++

 int getMissingNumber(vector<int>* input, int bitPos, const int startRange) { vector<int> zeros; vector<int> ones; int missingNumber=0; //base case, assume empty array indicating start value of range is missing if(input->size() == 0) return startRange; //if the bit position being tested is 0 add to the zero vector //otherwise to the ones vector for(unsigned int i = 0; i<input->size(); i++) { int value = input->at(i); if(getBit(value, bitPos) == 0) zeros.push_back(value); else ones.push_back(value); } //throw away either the odd or even numbers and test //the next bit position, build the missing number //from right to left if(zeros.size() <= ones.size()) { //missing number is even missingNumber = getMissingNumber(&zeros, bitPos+1, startRange); missingNumber = (missingNumber << 1) | 0; } else { //missing number is odd missingNumber = getMissingNumber(&ones, bitPos+1, startRange); missingNumber = (missingNumber << 1) | 1; } return missingNumber; } 

At each iteration, we reduce our input space by 2, i.e. N, N / 2, N / 4 ... = O (log N), with the space O (N)

 //Test cases [1] when missing number is range start [2] when missing number is range end [3] when missing number is odd [4] when missing number is even 

Answer 20

Solution With PHP $ n = 100 ;

 $n*($n+1)/2 - array_sum($array) = $missing_number 

and array_search($missing_number) will give the index of the missing number

Answer 21

 function solution($A) { // code in PHP5.5 $n=count($A); for($i=1;$i<=$n;$i++) { if(!in_array($i,$A)) { return (int)$i; } } } 

Answer 22

Here, the runtime complexity of the program is O (logn) and the complexity of the O (logn) space

 public class helper1 { public static void main(String[] args) { int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12}; int k = missing(a, 0, a.length); System.out.println(k); } public static int missing(int[] a, int f, int l) { int mid = (l + f) / 2; //if first index reached last then no element found if (a.length - 1 == f) { System.out.println("missing not find "); return 0; } //if mid with first found if (mid == f) { System.out.println(a[mid] + 1); return a[mid] + 1; } if ((mid + 1) == a[mid]) return missing(a, mid, l); else return missing(a, f, mid); } } 

Answer 23

 public class MissingNumber { public static void main(String[] args) { int array[] = {1,2,3,4,6}; int x1 = getMissingNumber(array,6); System.out.println("The Missing number is: "+x1); } private static int getMissingNumber(int[] array, int i) { int acctualnumber =0; int expectednumber = (i*(i+1)/2); for (int j : array) { acctualnumber = acctualnumber+j; } System.out.println(acctualnumber); System.out.println(expectednumber); return expectednumber-acctualnumber; } } 

Answer 24

Recently I had a similar (not quite the same) question in an interview, and I also heard from a friend who was asked exactly the same question in an interview. So, here is the answer to the OP question and a few more options that could potentially be requested. An example of the answers is given in Java because it stated that:

Preferred is a Java solution.

Solution 1:

Array of numbers from 1 to 100 (both inclusive) ... Numbers are randomly added to the array, but in the array

there is one random empty slot,

 public static int findMissing1(int [] arr){ int sum = 0; for(int n : arr){ sum += n; } return (100*(100+1)/2) - sum; } 

Explanation: This solution (like many other solutions posted here) is based on the Triangular number formula, which gives us the sum of all natural numbers from 1 to n (in this case, n is 100). Now that we know the amount, which should be from 1 to 100, we just need to subtract the actual amount of existing numbers in the given array.

Solution 2:

Array of numbers from 1 to n (this means that the maximum number is unknown)

 public static int findMissing2(int [] arr){ int sum = 0, max = 0; for(int n : arr){ sum += n; if(n > max) max = n; } return (max*(max+1)/2) - sum; } 

Explanation: In this solution, since the maximum number is not specified, we need to find it. After finding the maximum number - the logic is the same.

Solution 3:

Array of numbers from 1 to n (the maximum number is unknown), in the array

There are two random empty slots:

 public static int [] findMissing3(int [] arr){ int sum = 0, max = 0, misSum; int [] misNums = {};//empty by default for(int n : arr){ sum += n; if(n > max) max = n; } misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers for(int n = Math.min(misSum, max-1); n > 1; n--){ if(!contains(n, arr))misNums = new int[]{n, misSum-n}; } return misNums; } private static boolean contains(int num, int [] arr){ for(int n : arr){ if(n == num)return true; } return false; } 

Explanation: In this solution, the maximum number is not specified (as in the previous one), but two numbers may also be missing, not one. So, first we find the sum of the missing numbers - with the same logic as before. The second detection of a smaller number between the missing amount and the last (possibly) missing number - to reduce unnecessary search. Third, since Java Array (and not a collection) does not have methods like indexOf or contains , I added a small reuse method for this logic. Fourth, when the first missing number is found, the second is a subtraction from the missing amount. If only one number is missing, then the second number in the array will be zero.

Note

If you need examples from other languages or other interesting variations of this question , you can check out my Github repository for Questions and Answers Interviews .

Answer 25

Use the amount formula

 class Main { // Function to ind missing number static int getMissingNo (int a[], int n) { int i, total; total = (n+1)*(n+2)/2; for ( i = 0; i< n; i++) total -= a[i]; return total; } /* program to test above function */ public static void main(String args[]) { int a[] = {1,2,4,5,6}; int miss = getMissingNo(a,5); System.out.println(miss); } } 

Link http://www.geeksforgeeks.org/find-the-missing-number/

Answer 26

  //Array is shorted and if writing in C/C++ think of XOR implementations in java as follows. int num=-1; for (int i=1; i<=100; i++){ num =2*i; if(arr[num]==0){ System.out.println("index: "+i+" Array position: "+ num); break; } else if(arr[num-1]==0){ System.out.println("index: "+i+ " Array position: "+ (num-1)); break; } }// use Rabbit and tortoise race, move the dangling index faster, //learnt from Alogithimica, Ameerpet, hyderbad** 

Answer 27

If the array is randomly filled, then in the best case, you can perform a linear search for complexity O (n). However, we could improve O (log n) complexity by splitting and capturing, similar to quick sort, as pointed out by giri, given that the numbers were in ascending / descending order.

Answer 28

Now I am now too sharp with Big O notes, but could you also do something like (in Java)

 for (int i = 0; i < numbers.length; i++) { if(numbers[i] != i+1){ System.out.println(i+1); } } 

where numbers is an array with your numbers from 1 to 100. From my reading of the question, he did not say when to write out the missing number.

Alternatively, if you CAN throw the value i + 1 into another array and print it after iteration.

Of course, this may not comply with the rules of time and space. As I said. I have to comb my Big O hard.

Answer 29

Another question about homework. A consistent search is the best you can do. Regarding the Java solution, consider this exercise for the reader .: P

Answer 30

Quick sorting is the best choice with maximum efficiency ....