Quickest way to find 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  The numbers are randomly added to the array  but there is one random empty slot in the array   What is the quickest way to find that slot as well as the number that should be put in the slot  A Java solution is preferable

User · Answer

This was an Amazon interview question and was originally answered here: We have numbers from 1 to 52 that are put into a 51 number array, what's the best way to find out which number is missing?

It was answered, as 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.

It was also blogged here: Software Job - Interview Question

User · Answer

The solution that doesn t involve repetitive additions or maybe the n n 1  2 formula doesn t get to you at an interview time for instance   You have to use an array of 4 ints  32 bits  or 2 ints  64 bits   Initialize the last int with  -1  amp    1  lt  lt  31      3   the bits that are above 100 are set to 1  Or you may set the bits above 100 using a for loop    Go through the array of numbers and set 1 for the bit position corresponding to the number  e g  71 would be set on the 3rd int on the 7th bit from left to right  Go through the array of 4 ints  32 bit version  or 2 ints 64 bit version         public int MissingNumber int a                     int bits   sizeof int    8          int i   0          int no   0          while a i     -1   this means a i  s 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  lets say that the missing number is 58  That means that the 26th bit  left to right  of the second integer is set to 0   The first int is -1  all bits are set  so  we go ahead for the second one and add to  no  the number 32  The second int is different from -1  a bit is not set  so  by applying the NOT     operator to the number we get 64  The possible numbers are 2 at the power x and we may compute x by using log on base 2  in this case we get log2 64    6    32   32 - 6   58   Hope this helps

User · Answer

Let the given array be A with length N  Lets assume in the given array  the single empty slot is filled with 0   We can find the solution for this problem using many methods including algorithm used in Counting sort  But  in terms of efficient time and space usage  we have two algorithms  One uses mainly summation  subtraction and multiplication  Another uses XOR  Mathematically both methods work fine  But programatically  we need to assess all the algorithms with main measures like   Limitations like input values are large A 1   N   and or number of input values is large N   Number of condition checks involved Number and type of mathematical operations involved   etc  This is because of the limitations in time and or hardware Hardware resource limitation  and or software Operating System limitation  Programming language limitation  etc   etc  Lets list and assess the pros and cons of each one of them   Algorithm 1    In algorithm 1  we have 3 implementations    Calculate the total sum of all the numbers this includes the unknown missing number  by using the mathematical formula 1 2 3     N  N N 1   2   Here  N 100  Calculate the total sum of all the given numbers  Subtract the second result from the first result will give the missing number   Missing Number    N N 1   2  -  A 1  A 2      A 100   Calculate the total sum of all the numbers this includes the unknown missing number  by using the mathematical formula 1 2 3     N  N N 1   2   Here  N 100  From that result  subtract each given number gives the missing number   Missing Number    N N 1   2 -A 1 -A 2 -   -A 100    Note Even though the second implementation s formula is derived from first  from the mathematical point of view both are same  But from programming point of view both are different because the first formula is more prone to bit overflow than the second one if the given numbers are large enough   Even though addition is faster than subtraction  the second implementation reduces the chance of bit overflow caused by addition of large values Its not completely eliminated  because there is still very small chance since  N 1  is there in the formula   But both are equally prone to bit overflow by multiplication  The limitation is both implementations give correct result only if N N 1  lt  MAXIMUM NUMBER VALUE  For the first implementation  the additional limitation is it give correct result only if Sum of all given numbers lt  MAXIMUM NUMBER VALUE   Calculate the total sum of all the numbers this includes the unknown missing number  and subtract each given number in the same loop in parallel  This eliminates the risk of bit overflow by multiplication but prone to bit overflow by addition and subtraction     ALGORITHM missingNumber   0  foreach index from 1 to N        missingNumber   missingNumber   index        Since  the empty slot is filled with 0        this extra condition which is executed for N times is not required        But for the sake of understanding of algorithm purpose lets put it      if  inputArray index     0          missingNumber   missingNumber - inputArray index       In a programming language like C  C    Java  etc   if the number of bits representing a integer data type is limited  then all the above implementations are prone to bit overflow because of summation  subtraction and multiplication  resulting in wrong result in case of large input values A 1   N   and or large number of input values N    Algorithm 2    We can use the property of XOR to get solution for this problem without worrying about the problem of bit overflow  And also XOR is both safer and faster than summation  We know the property of XOR that XOR of two same numbers is equal to 0 A XOR A   0   If we calculate the XOR of all the numbers from 1 to N this includes the unknown missing number  and then with that result  XOR all the given numbers  the common numbers get canceled out since A XOR A 0  and in the end we get the missing number  If we don t have bit overflow problem  we can use both summation and XOR based algorithms to get the solution  But  the algorithm which uses XOR is both safer and faster than the algorithm which uses summation  subtraction and multiplication  And we can avoid the additional worries caused by summation  subtraction and multiplication   In all the implementations of algorithm 1  we can use XOR instead of addition and subtraction   Lets assume  XOR 1   N    XOR of all numbers from 1 to N  Implementation 1    Missing Number   XOR 1   N  XOR  A 1  XOR A 2  XOR   XOR A 100    Implementation 2    Missing Number   XOR 1   N  XOR A 1  XOR A 2  XOR   XOR A 100   Implementation 3       ALGORITHM missingNumber   0  foreach index from 1 to N        missingNumber   missingNumber XOR index        Since  the empty slot is filled with 0        this extra condition which is executed for N times is not required        But for the sake of understanding of algorithm purpose lets put it      if  inputArray index     0          missingNumber   missingNumber XOR inputArray index       All three implementations of algorithm 2 will work fine from programatical point of view also   One optimization is  similar to  1 2      N    N N 1   2   We have   1 XOR 2 XOR      XOR N    N if REMAINDER N 4  0  1 if REMAINDER N 4  1  N 1 if REMAINDER N 4  2  0 if REMAINDER N 4  3    We can prove this by mathematical induction  So  instead of calculating the value of XOR 1   N  by XOR all the numbers from 1 to N  we can use this formula to reduce the number of XOR operations   Also  calculating XOR 1   N  using above formula has two implementations  Implementation wise  calculating     Thanks to https   a3nm net blog xor html for this implementation xor    n gt  gt 1  amp 1      n amp 1  gt 0  1 n    is faster than calculating  xor    n   4    0    n    n   4    1    1    n   4    2    n   1   0    So  the optimized Java code is   long n   100  long a     new long n      XOR of all numbers from 1 to n    n 4    0 --- gt  n    n 4    1 --- gt  1    n 4    2 --- gt  n   1    n 4    3 --- gt  0    Slower way of implementing the formula    long xor    n   4    0    n    n   4    1    1    n   4    2    n   1   0    Faster way of implementing the formula    long xor    n gt  gt 1  amp 1      n amp 1  gt 0  1 n   long xor    n gt  gt 1  amp 1      n amp 1  gt 0  1 n    for  long i   0  i  lt  n  i          xor   xor   a i       Missing number System out println xor

User · Answer

One thing you could do is sort the numbers using quick sort for instance  Then use a for loop to iterate through the sorted array from 1 to 100  In each iteration  you compare the number in the array with your for loop increment  if you find that the index increment is not the same  as the array value  you have found your missing number as well as the missing index

User · Answer

This is c  but it should be pretty close to what you need   int sumNumbers   0  int emptySlotIndex   -1   for  int i   0  i  lt  arr length  i        if  arr i     0      emptySlotIndex   i    sumNumbers    arr i      int missingNumber   5050 - sumNumbers

User · Answer

Quick sort is the best choice with maximum efficiency

User · Answer

If the array is randomly filled  then at the best you can do a linear search in O n  complexity  However  we could have improved the complexity to O log n  by divide and conquer approach similar to quick sort as pointed by giri given that the numbers were in ascending descending order

User · Answer

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  lt  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

User · Answer

Well  use a bloom filter   int findmissing int arr    int n        long bloom 0      int i      for i 0  i lt  n  i   bloom  1 gt  gt arr i       for i 1  i lt  n   bloom lt  lt i  amp  1   i         return i

User · Answer

Recently I had a similar  not exactly the same  question in a job interview and also I heard from a friend that was asked the exactly same question in an interview   So here is an answer to the OP question and a few more variations that can be potentially asked   The answers example are given in Java because  it s stated that      A Java solution is preferable    Variation 1      Array of numbers from 1 to 100  both inclusive      The numbers are randomly added to the array  but there is one random empty slot in the array   public static int findMissing1 int    arr       int sum   0      for int n   arr           sum    n            return  100  100 1  2  - sum      Explanation  This solution  as many other solutions posted here  is based on the formula of Triangular number  which gives us the sum of all natural numbers from 1 to n  in this case n is 100   Now that we know the sum that should be from 1 to 100 - we just need to subtract the actual sum of existing numbers in given array    Variation 2      Array of numbers from 1 to n  meaning that the max number is unknown     public static int findMissing2 int    arr       int sum   0  max   0      for int n   arr           sum    n          if n  gt  max  max   n            return  max  max 1  2  - sum      Explanation  In this solution  since the max number isn t given - we need to find it  After finding the max number - the logic is the same    Variation 3      Array of numbers from 1 to n  max number is unknown   there is two random empty slots in the array    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  gt  max  max   n            misSum    max  max 1  2  - sum   Sum of two missing numbers     for int n   Math min misSum  max-1   n  gt  1  n--           if  contains n  arr                misNums   new int   n  misSum-n               break                         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 max number isn t given  as in the previous   but it can also be missing of two numbers and not one  So at first we find the sum of missing numbers - with the same logic as before  Second finding the smaller number between missing sum and the last  possibly  missing number - to reduce unnecessary search  Third since Javas Array  not a Collection  doesn t have methods as indexOf or contains  I added a small reusable method for that logic  Fourth when first missing number is found  the second is the subtract from missing sum   If only one number is missing  then the second number in array will be zero      Variation 4      Array of numbers from 1 to n  max number is unknown   with X missing  amount of missing numbers are unknown    public static ArrayList lt Integer gt  findMissing4 ArrayList lt Integer gt  arr       int max   0      ArrayList lt Integer gt  misNums   new ArrayList        int    neededNums      for int n   arr           if n  gt  max  max   n            neededNums   new int max    zero for any needed num     for int n   arr    iterate again         neededNums n    max   0   n      add one - used as index in second array  convert max to zero            for int i neededNums length-1  i gt 0  i--           if neededNums i   lt  1 misNums add i    if value is zero  than index is a missing number           return misNums      Explanation  In this solution  as in the previous  the max number is unknown and there can be missing more than one number  but in this variation  we don t know how many numbers are potentially missing  if any   The beginning of the logic is the same - find the max number  Then I initialise another array with zeros  in this array index indicates the potentially missing number and zero indicates that the number is missing  So every existing number from original array is used as an index and its value is incremented by one  max converted to zero      Note  If you want examples in other languages or another interesting variations of this question  you are welcome to check my Github repository for Interview questions  amp  answers

User · Answer

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 lt  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

User · Answer

Finding the missing number from a series of numbers  IMP points to remember    the array should be sorted   the Function do not work on multiple missings   the sequence must be an AP        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 lt max            int mid    min   max   gt  gt  gt  1          int leftDiff   array mid  - array min           if leftDiff  gt  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  gt  diff    max - mid                 if max-mid    1                  return  array max    array mid   2              min   mid              missingNum   false              continue                    if missingNum              break            return -1

User · Answer

simple solution with test data    class A     public static void main String   args       int   array   new int 200       for int i 0 i lt 100 i           if i    51           array i    i                       for int i 100 i lt 200 i           array i    i               int temp   0      for int i 0 i lt 200 i           temp    array i              System out println temp

User · Answer

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  lt  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

User · Answer

Below is the 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  lt  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  lt  lt  bit          bytes byteIndex     mask            for  int index   0  index  lt  bytes length - 2  index              if  bytes index     -128                for  int i   0  i  lt  8  i                      if   bytes index   gt  gt  i  amp  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  lt  loopTill  index              if   bytes bytes length - 1   gt  gt  index  amp  1     0                System out println  Missing number         bytes length - 1    8    index   1                        public static void main String   args         List lt Integer gt  arrayList   new ArrayList lt Integer gt         int n   128      int m   5      for  int i   1  i  lt   n  i              arrayList add i             Collections shuffle arrayList       for  int i   1  i  lt   5  i              System out println  Removing     arrayList remove i              int   array   new int n - m       for  int i   0  i  lt   n - m   i              array i    arrayList get i             System out println  Array is      Arrays toString array         findMissingNumbers n  array

User · Answer

This Program finds missing numbers   lt  php  arr num array  1   2   3   5   6     n count  arr num   for  i 1  i lt   n  i                   if  in array  i  arr num                 array push  arr num  i  print r  arr num  exit               gt

User · Answer

Here program take time complexity is O logn  and space complexity O logn   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

User · Answer

Solution With PHP  n   100    n   n 1  2 - array sum  array     missing number   and array search  missing number  will give the index of missing number

User · Answer

Here is a simple program to find the missing numbers in an integer array  ArrayList lt Integer gt  arr   new ArrayList lt Integer gt     int a       1 3 4 5 6 7 10    int j   a 0   for  int i 0 i lt 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

User · Answer

I think the easiest and possibly the most efficient solution would be to  loop over all entries and use a bitset to remember which numbers are set  and then test for 0 bit  The entry with the 0 bit is the missing number

User · Answer

On a similar scenario  where the array is already sorted  it does not include duplicates and only one number is missing  it is possible to find this missing number in 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

User · Answer

Simplest Solution for sorted Array             public int getMissingNumber int   sortedArray                        int missingNumber   0              int missingNumberIndex 0              for  int i   0  i  lt  sortedArray length  i                                  if  sortedArray i     0                                        missingNumber    sortedArray i   1   - 1                      missingNumberIndex i                      System out println  missingNumberIndex    missingNumberIndex                       break                                              return missingNumber

User · Answer

Now I m now too sharp with the Big O notations but couldn t you also do something like  in Java   for  int i   0  i  lt  numbers length  i          if numbers i     i 1           System out println i 1             where numbers is the array with your numbers from 1-100  From my reading of the question it did not say when to write out the missing number   Alternatively if you COULD throw the value of i 1 into another array and print that out after the iteration   Of course it might not abide by the time and space rules  As I said  I have to strongly brush up on Big O

User · Answer

Lets say you have n as 8  and our numbers range from 0-8 for this example we can represent the binary representation of all 9 numbers as follows 0000 0001 0010 0011 0100 0101 0110 0111 1000  in the above sequence there is no missing numbers and in each column the number of zeros and ones match  however as soon as you remove 1 value lets say 3 we get a in balance in the number of 0 s and 1 s across the columns  If the number of 0 s in a column is  lt   the number of 1 s our missing number will have a 0 at this bit position  otherwise if the number of 0 s   the number of 1 s at this bit position then this bit position will be a 1  We test the bits left to right and at each iteration we throw away half of the array for the testing of the next bit  either the odd array values or the even array values are thrown away at each iteration depending on which bit we are deficient on    The below solution is in C    int getMissingNumber vector lt int gt   input  int bitPos  const int startRange        vector lt int gt  zeros      vector lt int gt  ones      int missingNumber 0         base case  assume empty array indicating start value of range is missing     if input- gt size      0          return startRange         if the bit position being tested is 0 add to the zero s vector       otherwise to the ones vector     for unsigned int i   0  i lt input- gt size    i                  int value   input- gt 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    lt   ones size                    missing number is even         missingNumber   getMissingNumber  amp zeros  bitPos 1  startRange           missingNumber    missingNumber  lt  lt  1    0            else                 missing number is odd         missingNumber   getMissingNumber  amp ones  bitPos 1  startRange           missingNumber    missingNumber  lt  lt  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 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

User · Answer

This is not a search problem  The employer is wondering if you have a grasp of a checksum  You might need a binary or for loop or whatever if you were looking for multiple unique integers  but the question stipulates  one random empty slot   In this case we can use the stream sum  The condition   The numbers are randomly added to the array  is meaningless without more detail  The question does not assume the array must start with the integer 1 and so tolerate with the offset start integer    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

User · Answer

We can use XOR operation which is safer than summation because in programming languages if the given input is large it may overflow and may give wrong answer   Before going to the solution  know that A xor A   0  So if we XOR two identical numbers the value is 0    Now  XORing  1  n  with the elements present in the array cancels the identical numbers  So at the end we will 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 lt 100  i          if  ARRAY i     0     remove this condition keeping the body if no zero slot         XOR    ARRAY i       XOR     i   1     return XOR    return XOR   ARRAY length   1  if your array doesn t have empty zero slot

User · Answer

function solution  A           code in PHP5 5      n count  A       for  i 1  i lt   n  i             if  in array  i  A                   return  int  i

User · Answer

sum of 1 to n   -  sum of all values in the array    missing number  int sum   0  int idx   -1  for  int i   0  i  lt  arr length  i        if  arr i     0  idx   i  else sum    arr i     System out println  missing number is       5050 - sum      at index     idx

User · Answer

Use sum 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 lt  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               Reference http   www geeksforgeeks org find-the-missing-number

User · Answer

Another homework question  A sequential search is the best that you can do  As for a Java solution  consider that an exercise for the reader   P

User · Answer

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

[java] Quickest way to find missing number in an array of numbers

Examples related to java

Examples related to arrays

Examples related to algorithm