Array Missing Number
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
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
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
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; } } |
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]; } }