1
00:00:00,630 --> 00:00:08,670
In this video, we're going to solve this cutting interview question single number in this problem given

2
00:00:09,090 --> 00:00:12,150
in non empty area of integers nums.

3
00:00:13,290 --> 00:00:18,930
In this area every element appears to eight except for one.

4
00:00:19,500 --> 00:00:21,870
Find that single one.

5
00:00:22,890 --> 00:00:30,330
You must implement a solution with a linear runtime complexity and use only constant extra spit.

6
00:00:30,810 --> 00:00:32,490
This is the problem statement.

7
00:00:32,490 --> 00:00:43,140
In this problem we're given an array of integers and in that area we have every element appears to it

8
00:00:43,140 --> 00:00:48,000
except one, and we have to find out the single one.

9
00:00:48,780 --> 00:00:52,100
In this example, this area.

10
00:00:52,110 --> 00:00:56,070
In this area we see two appears twice and one appears once.

11
00:00:56,070 --> 00:01:06,930
So we have two region one in this example we see one appears twice to appear to part of appears one.

12
00:01:06,940 --> 00:01:12,900
So we have two written for and for this example we have only one element.

13
00:01:13,200 --> 00:01:14,640
Disillusioned appears one.

14
00:01:14,640 --> 00:01:16,590
So we have to return this element.

15
00:01:17,970 --> 00:01:19,920
Now how to solve this problem.

16
00:01:20,430 --> 00:01:22,950
We have a constraint.

17
00:01:22,950 --> 00:01:29,790
We have to solve this problem in linear runtime complexity and our algorithm should works in constant

18
00:01:30,150 --> 00:01:30,750
split.

19
00:01:31,830 --> 00:01:34,830
First, let's talk about the brute force solution.

20
00:01:35,900 --> 00:01:37,430
In the brute force solution.

21
00:01:38,460 --> 00:01:47,760
What I will do first I will construct a set that a structure lets I do this each hour set the structure

22
00:01:48,210 --> 00:01:54,060
in this said did a structure out store the non repetitive element.

23
00:01:54,480 --> 00:01:58,290
That means that the element that appears only once.

24
00:01:58,290 --> 00:02:00,420
But how we're going to do that.

25
00:02:01,920 --> 00:02:05,550
First thing, we have to traverse this area from left to right.

26
00:02:05,610 --> 00:02:08,460
First we have four weeks before doesn't exist.

27
00:02:08,460 --> 00:02:11,960
So let's insert here for now we have one.

28
00:02:11,970 --> 00:02:13,140
One does not exist.

29
00:02:13,140 --> 00:02:13,800
Never said two.

30
00:02:13,800 --> 00:02:18,180
Let's insert here one now two two does not exist.

31
00:02:18,180 --> 00:02:21,570
So let's insert two in our set.

32
00:02:22,230 --> 00:02:25,410
Now we have one and we set it just in our how set.

33
00:02:25,620 --> 00:02:28,590
So what I will do, I'll just remove one.

34
00:02:29,490 --> 00:02:31,830
Now we have the element two.

35
00:02:31,830 --> 00:02:35,400
We see two appears in this set to exist.

36
00:02:35,400 --> 00:02:37,500
So we'll remove this two.

37
00:02:37,950 --> 00:02:39,390
So let's remove this two.

38
00:02:39,630 --> 00:02:47,070
Now we see that we have only one element in our set and this is the single element.

39
00:02:47,370 --> 00:02:50,460
This element appears only once in the given area.

40
00:02:50,730 --> 00:02:52,770
So we have to return this element.

41
00:02:53,130 --> 00:02:57,690
This is how we can solve this problem using hash sit data structure.

42
00:02:58,110 --> 00:03:00,780
Now let's implement this algorithm.

43
00:03:01,350 --> 00:03:04,910
Now let's implement the brute force algorithm first thing.

44
00:03:04,920 --> 00:03:10,290
What we're going to do, we're going to check if the length of the error is one.

45
00:03:10,620 --> 00:03:14,070
It means that we have only one element in the array.

46
00:03:14,070 --> 00:03:15,570
We should return that element.

47
00:03:15,990 --> 00:03:18,420
So written nums is zero.

48
00:03:19,800 --> 00:03:22,710
Now let's create a hash set data structure.

49
00:03:23,100 --> 00:03:25,890
So set we'll store integer.

50
00:03:26,260 --> 00:03:29,250
Let's call it said equals to new heights it.

51
00:03:31,420 --> 00:03:33,550
Now we have to iterate the array from left to right.

52
00:03:33,550 --> 00:03:44,350
So for entirely close to zero I lived in nam stored lint I plus plots inside here all going to check

53
00:03:44,350 --> 00:03:47,830
if the current element contains in our city.

54
00:03:47,830 --> 00:03:53,890
Then you'll remove the current element from set, so let's check it.

55
00:03:54,250 --> 00:04:03,580
Said DOT contains if if the current element contains in our set sonam's enum now your current element.

56
00:04:03,580 --> 00:04:08,380
If our current element contains in the set, then it will remove from set.

57
00:04:08,380 --> 00:04:11,920
So say do not remove nums i.

58
00:04:14,550 --> 00:04:23,040
Otherwise, if if the element does not exist in our set, we will add the element to our set.

59
00:04:23,370 --> 00:04:26,190
So say did add nums a.

60
00:04:28,110 --> 00:04:35,700
When we're done with this fall off, we will have only one element in our set so we can retain that

61
00:04:35,700 --> 00:04:36,150
element.

62
00:04:36,390 --> 00:04:42,840
For that, I have to use this statement set dot, iterator, dot.

63
00:04:42,870 --> 00:04:50,790
Next we have to iterate over the grid, over the set, edit it over the set.

64
00:04:51,120 --> 00:04:53,700
We will get all the element just in the set.

65
00:04:53,730 --> 00:04:56,550
We have only one element in the set for sure.

66
00:04:56,820 --> 00:05:03,240
So we can we can just return, said Dot.

67
00:05:03,240 --> 00:05:12,390
Next, this algorithm will takes off in time, complexity and off in space complexity.

68
00:05:13,140 --> 00:05:14,970
Now let's run this code.

69
00:05:16,490 --> 00:05:17,250
Accepted.

70
00:05:17,330 --> 00:05:18,350
Now let's submit it.

71
00:05:20,060 --> 00:05:22,610
We have successfully solved this problem.

72
00:05:23,000 --> 00:05:25,200
But this is a brute force algorithm.

73
00:05:25,310 --> 00:05:27,140
We have a constraint to this problem.

74
00:05:27,150 --> 00:05:33,020
We have to solve this problem in constant in constant space complexity.

75
00:05:33,380 --> 00:05:35,720
Can you solve this problem in constant space?

76
00:05:35,720 --> 00:05:36,380
Complexity.

77
00:05:37,040 --> 00:05:43,010
Now, let's see how to improve this space complexity to constant space complexity.

78
00:05:43,930 --> 00:05:52,930
Let's assume we're given this array of integers in order to solve this problem in a constant space complexity

79
00:05:52,940 --> 00:05:56,830
we had to use XOR operator.

80
00:05:57,340 --> 00:06:05,590
We know for sure in the area we have some element appears tweet and only one element appears once.

81
00:06:06,400 --> 00:06:09,370
So we can use exert operator.

82
00:06:09,730 --> 00:06:25,480
We know the operation for two same bit it result in zero if we have to number here exert e it's results

83
00:06:25,480 --> 00:06:34,270
in zero if we apply exert operation in between, do same number, it will result in zero.

84
00:06:34,660 --> 00:06:34,990
Okay.

85
00:06:35,230 --> 00:06:38,530
This is the properties of exert operator.

86
00:06:38,800 --> 00:06:50,020
If we have something like this here exert zero, then it will be result in a again this is zero naught.

87
00:06:50,020 --> 00:06:55,480
Oh, we can solve this problem using the concept of XOR operator.

88
00:06:55,960 --> 00:07:03,070
Now what we will do will iterate the array from left to right and we'll applied the exit operator for

89
00:07:03,070 --> 00:07:04,030
old element.

90
00:07:04,030 --> 00:07:04,750
Something like this.

91
00:07:04,750 --> 00:07:05,680
First trip to.

92
00:07:05,950 --> 00:07:07,900
So to endure to.

93
00:07:08,770 --> 00:07:10,840
And then we will have one.

94
00:07:11,110 --> 00:07:14,200
So to exit to its result in zero.

95
00:07:14,740 --> 00:07:15,070
Okay.

96
00:07:15,460 --> 00:07:18,400
So we get here 001.

97
00:07:19,630 --> 00:07:24,730
So we get to 001001 equals two one.

98
00:07:25,540 --> 00:07:26,050
This is it.

99
00:07:26,320 --> 00:07:29,650
The element that appears only once in the area.

100
00:07:30,340 --> 00:07:32,590
So we have to return this element.

101
00:07:33,670 --> 00:07:36,850
Now, let's assume you're given this array of integers.

102
00:07:36,880 --> 00:07:42,040
Now let's apply exit operations in between all the numbers in the given array.

103
00:07:42,370 --> 00:07:53,980
So we have, for example, one for exer one exer to exert one, then exert two.

104
00:07:54,400 --> 00:07:58,150
Now what we see in here, we have two one.

105
00:07:58,420 --> 00:07:59,560
So one, one.

106
00:07:59,680 --> 00:08:01,120
It will be evaluated zero.

107
00:08:01,660 --> 00:08:03,260
And we have it to two.

108
00:08:03,640 --> 00:08:05,380
It will be evaluated zero.

109
00:08:05,620 --> 00:08:08,440
So for zero.

110
00:08:08,740 --> 00:08:11,410
For these two, it will be evaluated as zero.

111
00:08:12,520 --> 00:08:14,350
Then exert is zero.

112
00:08:15,820 --> 00:08:17,680
Now for these two.

113
00:08:18,940 --> 00:08:23,890
This comes from this welcome for this two and two.

114
00:08:24,220 --> 00:08:26,380
No 000 is zero.

115
00:08:26,650 --> 00:08:30,010
So four exerts zero four exert.

116
00:08:30,310 --> 00:08:32,020
Zero equal to for.

117
00:08:33,370 --> 00:08:37,990
This is the answer, and this element appears only once in the given area.

118
00:08:38,140 --> 00:08:43,180
So this is the single element or single number in the given area.

119
00:08:43,270 --> 00:08:44,230
This is the answer.

120
00:08:44,890 --> 00:08:51,640
This algorithm will take off in time complexes in which we have to traverse the array from left to right,

121
00:08:51,640 --> 00:08:53,650
and it will take speed of one.

122
00:08:53,900 --> 00:08:58,210
This space complexity, since we're using just one variable.

123
00:08:58,840 --> 00:09:01,720
Now let's see how to implement this algorithm.

124
00:09:02,680 --> 00:09:05,260
No, let's implement this algorithm.

125
00:09:06,040 --> 00:09:09,700
First, let's create a variable entry codes to the first element.

126
00:09:10,660 --> 00:09:17,080
We'll get the first element if we live in this area for one, two, one, two.

127
00:09:17,860 --> 00:09:20,370
We have two records to first eliminate.

128
00:09:20,530 --> 00:09:25,570
That means for now we have to iterate the array from the second index.

129
00:09:25,840 --> 00:09:34,800
So for intake holds to one i liz then nums dot lint i plus plot.

130
00:09:37,360 --> 00:09:37,840
No.

131
00:09:38,260 --> 00:09:39,880
Here, we have to.

132
00:09:40,150 --> 00:09:44,810
We have to apply to exert operations in building all the numbers.

133
00:09:44,830 --> 00:09:45,250
Okay.

134
00:09:46,060 --> 00:09:51,250
So answer equals to answer, exert numbers, height.

135
00:09:51,850 --> 00:09:56,500
And at the end, every region the answer you'll have the answer in this answer variable.

136
00:09:56,710 --> 00:09:57,730
How it works.

137
00:09:58,030 --> 00:10:00,280
Initially we have Anthony calls to four.

138
00:10:00,670 --> 00:10:12,010
Then if we apply this for love, then we get four, exert one, exert to exert one, exert two.

139
00:10:12,580 --> 00:10:16,120
So here this two and this two will be able to do zero.

140
00:10:16,930 --> 00:10:18,970
So we have zero.

141
00:10:19,390 --> 00:10:23,080
If we apply here zero and one will have the result one.

142
00:10:23,950 --> 00:10:26,890
Then the excellent between one and one is zero.

143
00:10:27,250 --> 00:10:31,810
We know the extrapolation in between same number result in zero.

144
00:10:32,350 --> 00:10:36,310
So the extrapolation in between four and zero is four.

145
00:10:37,060 --> 00:10:40,000
And this is our single number in this area.

146
00:10:40,480 --> 00:10:42,610
That means this number appears only once.

147
00:10:43,000 --> 00:10:52,900
This algorithm will takes bigger off in time complexity and it will takes bigger of one space complexity

148
00:10:53,470 --> 00:11:01,330
because we're using just one variable answer and let's around this code, it's accepted.

149
00:11:01,330 --> 00:11:02,350
Now let's submit it.

150
00:11:02,890 --> 00:11:09,360
We solved this problem, maintaining the constraint, linear time and constant spits.

151
00:11:09,670 --> 00:11:11,080
Thanks for watching this video.

152
00:11:11,360 --> 00:11:13,090
I will see you in the next video.