1
00:00:00,780 --> 00:00:02,520
Hi, everyone, welcome back.

2
00:00:02,550 --> 00:00:09,040
So in this video, we are going to solve this coin flip and let's discuss what this question is about.

3
00:00:09,360 --> 00:00:16,350
So it is saying you have a string nard string, you have a binary string by no means, zeros and ones.

4
00:00:16,530 --> 00:00:20,310
So you have a string and it is containing zeros and ones.

5
00:00:20,820 --> 00:00:21,260
Right.

6
00:00:21,630 --> 00:00:25,950
So you need to figure out two things left and right.

7
00:00:25,950 --> 00:00:28,140
So left means left index and right index.

8
00:00:28,500 --> 00:00:33,410
So after figuring out that this is left index, this is right index, what do you do?

9
00:00:33,450 --> 00:00:36,290
You will flip all the values.

10
00:00:36,300 --> 00:00:40,020
So for example, this is your left and this is your right and left.

11
00:00:40,050 --> 00:00:42,130
These are zero one and one.

12
00:00:42,420 --> 00:00:46,990
So what you will do if you are saying this is left and this is right, you will flip all the values.

13
00:00:47,010 --> 00:00:48,710
So this is when it will become zero.

14
00:00:48,870 --> 00:00:49,820
It will become one.

15
00:00:49,830 --> 00:00:50,730
It will become zero.

16
00:00:50,730 --> 00:00:51,570
It will become one.

17
00:00:51,570 --> 00:00:52,500
It will become zero.

18
00:00:52,500 --> 00:00:53,370
It will become zero.

19
00:00:53,460 --> 00:00:57,210
So that is the meaning of flip, right.

20
00:00:57,450 --> 00:01:05,190
Flip means convert zero to one and one to zero in the range L2 are so given the string lozzi, given

21
00:01:05,190 --> 00:01:05,750
the string.

22
00:01:06,120 --> 00:01:11,700
And one more thing, this operation, this flipping operation, we can perform this operation only once

23
00:01:12,270 --> 00:01:18,140
at the max, once it is not necessary that we will do flip operation.

24
00:01:18,150 --> 00:01:22,210
But if you want to do flip operation at Max, you can do only one time.

25
00:01:23,190 --> 00:01:29,940
So given the string, my aim, my aim of flipping is basically to create a maximum number of buttons

26
00:01:29,940 --> 00:01:35,160
and then you string to basically maximize one in the newly created string.

27
00:01:35,170 --> 00:01:36,750
That is the ultimate aim.

28
00:01:38,370 --> 00:01:45,480
Right, so I'm repeating myself, given a string string will contain a binary thing, so it will contain

29
00:01:45,480 --> 00:01:46,750
obviously zeros and ones.

30
00:01:48,030 --> 00:01:53,550
My aim is to maximize the number of points in the string and for maximizing the number of ones.

31
00:01:53,550 --> 00:01:59,330
Answering the question is providing us option that you can flip and what values you can flip.

32
00:01:59,340 --> 00:02:02,120
So all the values between left and right you can flip.

33
00:02:02,340 --> 00:02:05,030
And how do we figure out the values of left and right?

34
00:02:05,040 --> 00:02:06,340
That is your question.

35
00:02:06,630 --> 00:02:13,860
So you need to figure out the values of left and right such that if you flip all the values from left

36
00:02:13,860 --> 00:02:18,750
to right, the number of ones in the newly created string will be maximized.

37
00:02:19,200 --> 00:02:19,590
Right.

38
00:02:19,740 --> 00:02:23,650
So in this example, this is my by zero one zero.

39
00:02:24,030 --> 00:02:25,110
And this is simple.

40
00:02:25,110 --> 00:02:27,980
ELLENDER So when and when replace this.

41
00:02:28,260 --> 00:02:31,950
So this thing will become one one zero, then one and two left is one, right.

42
00:02:32,130 --> 00:02:32,390
Two.

43
00:02:32,430 --> 00:02:33,700
So I will replace these two.

44
00:02:34,050 --> 00:02:36,450
So it will become one zero zero in this case.

45
00:02:36,450 --> 00:02:37,170
One, two, three.

46
00:02:37,440 --> 00:02:43,110
So one, two, three means flip the entire string so it will become one zero one zero one, then two

47
00:02:43,110 --> 00:02:43,550
to three.

48
00:02:43,560 --> 00:02:49,150
So replace these two characters so it will become zero zero and one.

49
00:02:49,620 --> 00:02:51,030
OK, so this is two and two.

50
00:02:51,300 --> 00:02:53,400
So it means zero zero zero.

51
00:02:53,400 --> 00:02:53,690
Right.

52
00:02:53,700 --> 00:02:54,870
And this is two and three.

53
00:02:55,080 --> 00:02:56,600
So that means these two characters.

54
00:02:56,940 --> 00:02:58,810
So it becomes zero zero and one.

55
00:02:59,280 --> 00:03:04,540
So in this and in this, we have two ones.

56
00:03:05,610 --> 00:03:08,220
So number of once the count of onces two.

57
00:03:08,460 --> 00:03:16,110
So my answer can be this one and my answer can be this one, because both of these are giving me equal

58
00:03:16,110 --> 00:03:17,040
number of wins.

59
00:03:17,400 --> 00:03:17,740
Right.

60
00:03:17,940 --> 00:03:20,610
So these are the maximum number of wins in the new string.

61
00:03:20,670 --> 00:03:24,400
Now, the question is, what should be done at this one or this one?

62
00:03:25,200 --> 00:03:31,350
Now, it does give an indication that if you have more than one possible answer, more than one possible

63
00:03:31,350 --> 00:03:35,520
combination of Ellender are giving you the maximum number of wins.

64
00:03:35,520 --> 00:03:37,560
That is equal number of maximum ones.

65
00:03:38,040 --> 00:03:41,650
Then you need to report your answer if the lexicographical is smallest.

66
00:03:42,030 --> 00:03:43,970
So what do you mean by lexicographical smallest?

67
00:03:44,250 --> 00:03:45,150
So we will compare.

68
00:03:45,150 --> 00:03:47,730
This is one and this is an OK.

69
00:03:47,780 --> 00:03:48,360
They are equal.

70
00:03:48,390 --> 00:03:49,500
Now compare the value of.

71
00:03:49,500 --> 00:03:49,840
Right.

72
00:03:50,130 --> 00:03:52,160
So this is one and this is three.

73
00:03:52,590 --> 00:03:53,860
So one is less than three.

74
00:03:54,090 --> 00:03:55,710
So this will be my answer.

75
00:03:55,720 --> 00:03:57,390
My answer will be one and one.

76
00:03:58,350 --> 00:04:00,900
So that is the meaning of lexicographical smallest.

77
00:04:01,470 --> 00:04:02,910
Now let's see this example.

78
00:04:03,840 --> 00:04:10,890
So in this example, all the values are on alert, even in this case, what the value of and are I told

79
00:04:10,890 --> 00:04:16,040
you at the max you can do this operation once, but this operation is optional.

80
00:04:16,170 --> 00:04:17,550
If you want to do it, we can.

81
00:04:17,820 --> 00:04:19,589
If you don't want to do it, then don't do it.

82
00:04:19,769 --> 00:04:26,490
So in this case, we will not perform flip operation because all the values are already when and if

83
00:04:26,490 --> 00:04:27,390
we are not flipping.

84
00:04:27,390 --> 00:04:30,450
That means the value of left and right are not defined.

85
00:04:30,990 --> 00:04:34,140
And if they are not defined, I will return ampitheater.

86
00:04:36,090 --> 00:04:42,380
If left and right does not exist, then I will return empty array and if left cannot exist, then what

87
00:04:42,390 --> 00:04:46,040
I will do so in Inari I will create an area of size two.

88
00:04:46,050 --> 00:04:50,070
I will insert left, I will insert right, and I will return this area.

89
00:04:50,520 --> 00:04:52,350
So that is the problem statement.

90
00:04:53,590 --> 00:04:59,520
I hope you understood the question and now we need to think how we can solve this question.

91
00:05:00,910 --> 00:05:02,040
So it's very simple.

92
00:05:02,380 --> 00:05:05,960
It's actually the variation of Caden's algorithm.

93
00:05:06,130 --> 00:05:08,660
So how could an algorithm will help us here?

94
00:05:09,220 --> 00:05:10,810
Let me take one example.

95
00:05:11,020 --> 00:05:15,610
OK, so let's take one example and let's try to understand how this will work.

96
00:05:15,670 --> 00:05:23,100
So this is this is my string zero zero one one one zero.

97
00:05:24,250 --> 00:05:26,800
I want to find out the value of left and right.

98
00:05:27,280 --> 00:05:33,490
So by observation, I can tell that the value of left is one and the value of right is two.

99
00:05:33,730 --> 00:05:37,840
So if we will flip these two, then what will happen?

100
00:05:37,840 --> 00:05:40,990
The string will become one one one, one one and zero.

101
00:05:41,230 --> 00:05:44,080
So this string is containing five ones.

102
00:05:44,380 --> 00:05:45,670
So that will be our answer.

103
00:05:45,670 --> 00:05:46,050
Right.

104
00:05:46,180 --> 00:05:52,870
So these are the makes a number of ones that can be possible to what Caden's algorithm says, but we

105
00:05:52,870 --> 00:06:01,840
will do so either replace zero by one and I will replace one by minus one night.

106
00:06:02,020 --> 00:06:10,030
But we need to do we need to maximize the number of ones and how we can maximize number of ones by flipping

107
00:06:10,030 --> 00:06:11,880
zero to one late.

108
00:06:12,130 --> 00:06:15,440
So by flipping 021 one, I can maximize the number of ones.

109
00:06:15,460 --> 00:06:19,570
So that means whenever we encounter zero, I will treat it as one.

110
00:06:19,900 --> 00:06:23,220
And whenever we encounter one, I will treat it as minus one.

111
00:06:23,560 --> 00:06:28,450
So I know this seems very weird, but this is the trick for solving this question.

112
00:06:28,450 --> 00:06:28,740
Right.

113
00:06:29,050 --> 00:06:33,010
And how district will help us see this is your string, right?

114
00:06:33,040 --> 00:06:34,260
This is your input string.

115
00:06:34,480 --> 00:06:35,650
So let's apply this.

116
00:06:36,010 --> 00:06:41,570
Let's try to replace the zero means one one and one means minus one.

117
00:06:41,590 --> 00:06:43,390
So this is minus one, minus one.

118
00:06:43,660 --> 00:06:45,350
Minus one and zero minus one.

119
00:06:45,370 --> 00:06:49,120
So this is your new string according to this formula, right?

120
00:06:49,930 --> 00:06:51,080
According to this formula.

121
00:06:51,100 --> 00:06:52,330
This is my new string.

122
00:06:53,900 --> 00:07:04,480
I'll run Caden's algorithm, so what Caden's algorithm gives us, it gives us the maximum sum contiguous

123
00:07:04,490 --> 00:07:05,150
Sabeti.

124
00:07:06,230 --> 00:07:12,500
And what will be the maximum contiguous average this this will be the maximum contiguous average and

125
00:07:12,500 --> 00:07:14,950
the sum is to date.

126
00:07:15,470 --> 00:07:19,000
So what we need to do, we need to find out the maximum some contiguous.

127
00:07:19,000 --> 00:07:23,100
Sabeti So this is the maximum savary and the sum is two.

128
00:07:23,870 --> 00:07:26,410
So this will be my left and this will be my right.

129
00:07:27,920 --> 00:07:29,200
And that is the right answer.

130
00:07:29,210 --> 00:07:29,560
Right.

131
00:07:31,540 --> 00:07:32,810
Let me take one more example.

132
00:07:32,820 --> 00:07:36,410
Let's take this example, which is give given indication this one.

133
00:07:37,790 --> 00:07:43,000
So let's convert this string on basis of this tricky part.

134
00:07:43,310 --> 00:07:46,700
So replace zero with one and replace one with minus one.

135
00:07:47,240 --> 00:07:49,520
So this will be your new string.

136
00:07:50,330 --> 00:07:50,720
Right.

137
00:07:50,960 --> 00:07:56,150
And what we will do, we will then condense algorithm on this to find out the maximum Sabeti size,

138
00:07:56,630 --> 00:07:57,710
maximum symbolism.

139
00:07:58,100 --> 00:08:00,040
So here we have two possibilities.

140
00:08:01,400 --> 00:08:06,070
The maximum Subedi for this is one, and we have one more possibility.

141
00:08:06,380 --> 00:08:07,800
So sum is one.

142
00:08:08,600 --> 00:08:11,950
So we have two possibilities right here.

143
00:08:11,960 --> 00:08:13,100
We have two possibilities.

144
00:08:13,280 --> 00:08:18,130
So this will be the value of left and right, and this will be the value of left and right.

145
00:08:18,470 --> 00:08:21,100
So that means this is index zero.

146
00:08:21,590 --> 00:08:24,900
But in this case, we need to report our answer as indexing one.

147
00:08:25,280 --> 00:08:29,000
So one common one can be our answer or this.

148
00:08:29,900 --> 00:08:32,150
This is Tecoma three can be our answer.

149
00:08:34,679 --> 00:08:34,940
Right.

150
00:08:35,210 --> 00:08:36,780
So two answers are possible.

151
00:08:37,159 --> 00:08:47,930
So when government means convert this into one one zero and three, three means convert it to zero one

152
00:08:47,930 --> 00:08:49,200
and one night.

153
00:08:49,250 --> 00:08:50,720
So two answers are possible.

154
00:08:51,050 --> 00:08:55,300
And what we need to do, we need to report our answer is minimum, lexicographical minimum.

155
00:08:55,320 --> 00:08:57,180
So I will report my answer is this one.

156
00:08:58,640 --> 00:08:58,870
So.

157
00:08:58,880 --> 00:08:59,120
Right.

158
00:08:59,180 --> 00:09:01,460
What we need to do, very, very simple.

159
00:09:02,030 --> 00:09:07,520
Whenever you encounter zero or replace it with one, whenever you encounter one, replace it with minus

160
00:09:07,520 --> 00:09:12,830
one, then find out the maximum some Saberi, you will be able to find out the maximum sum.

161
00:09:12,830 --> 00:09:19,580
Sabeti And the starting point of the maximum some somebody will be left and the ending point will be

162
00:09:19,580 --> 00:09:19,880
are.

163
00:09:21,080 --> 00:09:23,690
So that's how you will be able to solve this question.

164
00:09:23,930 --> 00:09:25,830
Let me take one more example.

165
00:09:26,150 --> 00:09:33,730
So let's say I have one when and then zero zero zero zero and then one and then again do right.

166
00:09:34,280 --> 00:09:39,650
So according to the trick or Tulu one means this is minus one.

167
00:09:39,660 --> 00:09:40,340
This is minus one.

168
00:09:40,370 --> 00:09:42,080
This is when, when, when, when.

169
00:09:42,290 --> 00:09:43,190
This is minus one.

170
00:09:43,190 --> 00:09:46,700
And this is when applied Caden's algorithm.

171
00:09:47,390 --> 00:09:49,370
So this will be the maximum sum.

172
00:09:49,370 --> 00:09:51,810
Saberi and the sum is four.

173
00:09:52,250 --> 00:09:54,510
So the starting point will be the left.

174
00:09:54,530 --> 00:09:57,470
This is my left and the ending point will be my right.

175
00:09:57,830 --> 00:09:59,310
So this is the value of left.

176
00:09:59,570 --> 00:10:00,950
And this is the value of right.

177
00:10:01,790 --> 00:10:04,100
So that's how you will be able to find out.

178
00:10:04,130 --> 00:10:05,930
You will be able to solve this question.

179
00:10:06,560 --> 00:10:08,270
So this is index zero one.

180
00:10:08,270 --> 00:10:14,350
This is index to left is index two, three, four, five, and right this index six.

181
00:10:14,720 --> 00:10:19,970
So you will report your answer as three, comma seven, because it is giving the question that you need

182
00:10:19,970 --> 00:10:22,940
to report the answer by one indexing this.

183
00:10:23,540 --> 00:10:23,910
Right.

184
00:10:23,990 --> 00:10:25,590
So this is zero one two.

185
00:10:25,850 --> 00:10:30,530
I read the index is two, but we need to add plus one when we will report our answer.

186
00:10:30,890 --> 00:10:36,230
Similarly, the right values six, but we will add plus one when we will report our answer.

187
00:10:36,620 --> 00:10:39,040
So that's how you can use them.

188
00:10:39,410 --> 00:10:44,810
So I highly recommend that you try according this problem and if you are able to do it, then it's very

189
00:10:44,810 --> 00:10:45,040
good.

190
00:10:45,050 --> 00:10:50,570
Otherwise you can always watch this in our next video so that good guys, I will meet you in the next

191
00:10:50,570 --> 00:10:50,790
one.

192
00:10:50,810 --> 00:10:51,380
Thank you.