FilesExpand file tree

 master

/

singleNumber.III.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

94 lines (88 loc) · 3.14 KB

 master

/

singleNumber.III.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

94 lines (88 loc) · 3.14 KB

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

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

// Source : https://leetcode.com/problems/single-number-iii/

// Author : Hao Chen

// Date : 2016-01-16

/***************************************************************************************

*

* Given an array of numbers nums, in which exactly two elements appear only once and

* all the other elements appear exactly twice. Find the two elements that appear only

* once.

*

* For example:

*

* Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

*

* Note:

*

* The order of the result is not important. So in the above example, [5, 3] is also

* correct.

* Your algorithm should run in linear runtime complexity. Could you implement it using

* only constant space complexity?

*

* Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating

* all test cases.

***************************************************************************************/

/*

* For the problem - only one number appears once when all other numbers appears exactly twice.

*

* We know, we can XOR all of the array elements. Since X^X is zero, and X^0 is X,

* so all of the duplicated number will zero themselves out, and the only number would be the result.

*

* However, this solution cannot be applied directly to finding two numbers that appear once each.

*

* Suppose that these numbers that appear once are X and Y, and all other numbers appear twice.

* If we decide to XOR all the array's elements, the overall result would actually be `X^Y`.

*

* Unfortunately, there is no way to extract J and K out of their XOR.

*

* But since X and Y are different, we are sure that X^Y is different than zero.

*

* This information is valuable in sense that we know pieces of information that differ.

* If we pick up any bit that is 1 in X XOR Y, we can use it as a mask to test each element of the array.

*

* Obviously, that mask will be the discriminator between X and Y -

*

* Only one of them will have value 1 at that particular position.

*

*

* Now that we have the mask with exactly one bit set to 1, we can walk through the array once again.

*

* But this time we are going to maintain two XORed results.

*

* - One for numbers that have bit 1 at the mask's position

* - Another for numbers that have bit 0 at that position

*

* In this way, we are sure that all duplicates will go into the same pile.

*

* But likewise, we are sure that X and Y will go into separate piles.

*

* So, the overall result is that

* - the first XORed result will be equal to X

* - and the second XORed result will be equal to Y

*

*/

class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

int allxor = 0;

for (int n : nums) {

allxor ^= n;

}

int mask = 1;

while ( (mask & allxor) == 0 ) {

mask <<= 1;

}

int zero = 0;

int one = 0;

for (int n : nums) {

if (n & mask ){

one ^= n;

}else {

zero ^= n;

}

}

vector<int> result;

result.push_back(zero);

result.push_back(one);

return result;

}

};