IBM Interview Question

SKFrankChen

This question comes from my interview with IBM about 5 years ago.

Given 99 integers ranged from 1 to 100( no duplicate numbers),  design an algorithm to find out which number is missing between 1 and 100.

bleem1998

1. 
   
2. int func(int *p) {
   
3.    int i, array[101];
   
4.    bzero(array, 101);
   
5.    for(i = 1; i < 101; i++)
   
6.       array[p[i]] = 1;
   
7.    for(i = 1; i < 101; i++)
   
8.       if (array[i] == 0)
   
9.          return i
   
10.    return -1
    
11. }
    

复制代码

bleem1998

上面那个有八哥
大致思路就是用bitmap
再写个python的

1. 
   
2. #python
   
3. def func(rang_int):
   
4.    yy = range(1,100)
   
5.    for i in yy:
   
6.       if i not in rang_int:
   
7.          return i
   
8.    return -1
   

复制代码

maluyao

(1+100)*50 =5050
5050 - 其余数字之和就是缺的数字

converse

算出1到100的数之和
算出那99个数的和
相减就可以了

bleem1998

high...