Find the missing number

Computer Science Level 2

There is an array A 1 A_{1} and another array A 2 A_{2} which is an exact copy of the first array. By accident one of the numbers from the second array is deleted. What is the deleted number?

Note : array1 and array2 .

It is recommended to devise an efficient solution.


The answer is 2069.

View wiki
Beakal Tiliksew by Beakal Tiliksew , 24, Ethiopia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

6 solutions

Abdelhamid Saadi
Jun 1, 2016

Compare the elements in the middle of the list:

  • if equal then the difference is is the second half of the list.

  • if not equal then the difference is the first half of the list.

then repeat the process for the half containing the difference.

This algorithm is in l o g ( N ) log(N)

4 Helpful 0 Interesting 0 Brilliant 0 Confused

sure, but only works if there are no repeated numbers, otherwise you have to check the surroundings.

J T - 1 year, 7 months ago

You are right.

Abdelhamid Saadi - 1 year, 7 months ago

It is known that there is one element from Array-1 that is missing in Array-2.

So the simplest algorithm would be :

  1. Extract all elements of the two arrays in two lists (say List1 and List2)

  2. Required element would be sum(List1)-sum(List2)

Note : It would have been much more challenging had there been more than one element missing, or two elements had swapped places etc.

2 Helpful 0 Interesting 1 Brilliant 0 Confused

Python 3.5.1: 

array1 = open("array1.txt","r")
array2 = open("array2.txt","r")
array1list = []
array2list = []
for line in array1:
    values=line.strip().split(",")
    for i in values:
        array1list.append(i)
for line in array2:
    values=line.strip().split(",")
    for i in values:
        array2list.append(i)
for i in array2list:
    array1list.remove(i)

print (array1list)
1 Helpful 0 Interesting 0 Brilliant 0 Confused

just use array1 - array2

Viki Zeta - 5 years ago

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Rushikesh Jogdand
Jul 10, 2016 
1
2
3
4
5
 
with open('/home/rushi/Downloads/a1.txt','r') as f:
    exec('a1=['+f.read()+']')
with open('/home/rushi/Downloads/a2.txt','r') as f:
    exec('a2=['+f.read()+']')
print(sum(a1)-sum(a2))

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...