December 9, 2010
HomeAlgorithms and Data StructuresArray Missing Number

Array Missing Number

By  Algorithms and Data Structures  1 Comment

Problem

Given an array of n-1 unique integers. Each element in the array is an integer between 1 and n. Write a program to print the missing number in the array

Solution

To clarify this problem let us take a simple example. Assume n = 3 so the array consists from two elements only. Here are some possible values of the array in the range 1 .. 3

C++
1
2
3
1 2 : missing element is 3
1 3 : missing element is 2
2 3 : missing element is 1

Let us solve this problem using brute force first. We need two nested loops. The outer loop goes through all numbers between 1 and n while the inner loop searches the array for the outer loop current index. If it is found then you continue. If you do not find it then it is the missing number

Code

Here is the code in Perl

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#!/usr/bin/perl
 
# This array consists from 9 elements
# Since n = 10 the missing element is 7
@array = (10, 3, 5, 1, 9, 2, 4, 6, 8);
 
# Check all numbers between 1 and 10
for ($i = 1; $i <= 10; $i++)
{
# Found = 0 means number is missing
$found = 0;
 
        # Search for the current number i
        # in the array
for $element (@array)
{
         # If the number is found then exit
                # loop and move to the next number
if ($element == $i)
{
$found = 1;
last;
}
}
 
        # If found is still 0 then this means the
        # number is not found in the array in other
        # words it is the missing element
if ($found == 0)
{
print "Missing element = " . $i . "\n";
}
}

Solution

The brute force solution runs in O(nxn) but we can do better and solve this problem in linear time if we hash the array elements

Code

Here is we are going to do it in Perl

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#!/usr/bin/perl
 
# This array consists from 9 elements
# Since n = 10 the missing element is 7
@array = (10, 3, 5, 1, 9, 2, 4, 6, 8);
 
# Let us hash the array elements
for $element (@array)
{
$Hash{$element} = $element;
}
 
# Check all numbers between 1 and 10
for ($i = 1; $i <= 10; $i++)
{
$found = 0;
 
        # If the number is found in the
        # hash then it is not missing
if ($Hash{$i} == $i)
        {
         $found = 1;
        }
 
        # Number is not in the hash meaning it is missing
        # Quit search we are done
        if ($found == 0)
        {
         print "Missing number = " . $i . "\n";
                last;
        }
}

More from my site

Tags:,

About Author

Mohammed Abualrob

Software Engineer @ Cisco

One Comment
  1. greenhopes

    the hash algorithm needs o(n) space, use xor operator you can have o(1) space and o(n) run time
    code in java

    public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 6, 7, 8};
    int ret = 1^2^3^4^5^6^7^8;

    for (int i = 0 ; i < a.length ; i++){ ret = ret ^ a[i]; } }

    Reply

Add a Comment

Your email address will not be published. Required fields are marked *