FilesExpand file tree

 master

/

find_missing_num.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (40 loc) · 977 Bytes

 master

/

find_missing_num.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (40 loc) · 977 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

34

35

36

37

38

39

40

41

42

43

44

45

46

47

/*

* Find the missing number in an array [1...N].

* The array has N-1 numbers, missing one in between.

*

* Algorithm:

* Naive: just sum up the number in the array

* and compare to the sum from 1 to N,

* the diff is the missing number.

* Problem: the sum could overflow if it's a stream

*

* Good:

* XOR every number in array --> xor_1

* XOR every number from 1 to N --> xor_2

*

* xor_1 ^ xor_2 is the missing number

*

*/

#include <iostream>

using namespace std;

int findMissingNum(int a[], int len, int N)

{

int expected = 0;

int actual = 0;

int i;

for(i=1; i<=N; i++) {

expected ^= i;

}

for(i=0; i<len; i++) {

actual^=a[i];

}

return (expected^actual);

}

int main()

{

int a[] = {1, 3, 2, 4, 7, 6};

int len = sizeof(a)/sizeof(a[0]);

int N = 7;

cout << "missing: " << findMissingNum(a, len, N) << endl;

return 0;

}