foreign [Music] welcome back to my YouTube channel in this particular video we'll be looking into a very interesting and important algorithm which is widely used in data streams the algorithm is called as datar geonis indic motwani algorithm the name of this algorithm is pretty much long and difficult hence there is a shorter version for this the algorithm is commonly called as motwani algorithm or digim you can also call it as dgim so this particular algorithm is specifically used to find the number of ones in a given stream of data the stream will be continuous and it will be huge so whenever we want to count any specific element occurrence in the given stream of data then we can use this particular algorithm the specialty of this algorithm is that it uses logarithmic space to represent a window of n Bits so if a given stream contains total n Bits then this algorithm is not going to take all the N bit space rather it will take the logarithmic space to represent the entire set of n Bits now one more advantage of this particular algorithm is that the probability of getting correct result will always be greater than 50 percent so I hope you have got an overview of this particular motwani algorithm now to start with the insights of this algorithm we'll have to see first the elements that are associated with this particular algorithm so the first element is timestamp so in a given stream of data the elements continuously comes inside the window so each element that is entering in the Stream will be allotted a specific timestamp which will be based on the position of it in short the position of that particular element will be taken as the timestamp for example the timestamp for the first bit that has entered into the stream will be 1. the second bit time stamp will be 2 the third bit will be 3 and so on and so forth I hope the timestamp concept is clear this was the first element now let's have a look at the second element which is buckets this is the most important element inside this particular algorithm now buckets are used to represent the time intervals in a given data stream that means it is going to create specific sections from that data streams which will be dynamically created and it is going to be a continuous process now as I said the algorithm divides the entire stream into buckets now each bucket will have a size of the power of 2. there are certain constraints for bucket we will be looking into it next for now just remember that buckets contains the bits zeros and ones now we are done with the elements of the motwani algorithm now let's have a look at the rules and regulations that we need to follow while forming a bucket so bucket formation is a confusing process but trust me I'll make it very much clear and simple for you by the end of this video the first rule for bucket is that every bucket should contain at least a single one inside it as you know that the bucket contains zeros and ones a valid bucket will always contain at least one single one inside it so you can see the first example contains four ones which satisfies the condition in the second example you can see there is no single one inside it hence it's not a valid bucket I hope the first rule is clear now coming to the second rule the second rule says that the right side of the bucket that means the rightmost bit of the bucket should always have a one the bit must be one strictly otherwise the bucket will not be a valid one so you can see the first example here you can see the last rightmost bit is one hence this is a valid bucket in the second example you can see that the rightmost bit is zero hence this is not a valid bucket so I hope the difference is clear and by this the second rule must be clear to you all so let's have a look at the third rule the third rule is about calculating the length of the bucket so the length of the bucket will be calculated by the number of ones inside it so let's say if a bucket contains four ones in it so the length of that particular bucket will be 4. so here you can see an example here we have 1 0 1 0 0 1 1 this is the bits that we have inside the bucket and it contains total four ones hence the length of the bucket will be four so I hope this particular rule is clear to you all so moving on to the next rule the fourth rule says that every bucket length should be in the powers of 2 that means the length of the bucket should be 2 to the power 0 it can be 2 to the power 1 2 to the power of 2 and so on so you can see 2 to the power 0 is 1 2 to the power 1 is 2 2 to the power 2 is 4 so the bucket length can be 1 2 4 8 16 32 and so on if the bucket length is not satisfying this particular criteria then it will not be counted as a valid bucket so you can see in the first example we have the length of the bucket as 4 which is a power of 2 which is nothing but 2 to the power 2 so it is a valid bucket but if we consider the second example which is this it contains three ones hence the length will be three as you know three doesn't comes in the powers of two therefore this is not a valid bucket so I hope this particular difference is clear and this is again a very important rule to remember the fifth rule says that as we move from right to left the bucket set size should strictly not decrease while forming the buckets inside a stream we should start from the right side it is better to start from the right end and while creating the buckets you should remember that as you are starting from right and you are moving to left the size of the bucket should increase it should not decrease so let's consider this particular stream and we are trying to create buckets from the right side so you can see the first bucket contain the length 2 the second bucket contains the length one the third bucket contains the length fourth and the fourth bucket contains the length 2. as we are moving from right to left the bucket length has got decreased hence this is not valid way to create buckets let's take this same stream and let's try to create buckets so from the very right side if we start we are going to start with the bucket of length one then we'll create bucket of length 2 then a bucket of length 2 again note that here we are not decreasing the size the size is constant the fourth bucket is of length four so you can see as we are moving from right to left the size of the bucket is increasing so it is a valid example for creating buckets so I hope this particular rule is very much clear to you all a little practice will always help a lot so practice now let's move on to the last rule it says that no more than two buckets should be of the same size if you remember in the previous example we created two buckets of same length that was two so that is valid if you create two buckets of same length it is valid but if you create more than two buckets of same length then it is not valid so in this particular example you can see that we already have created two buckets of length two now if we try to create the third bucket again of length 2 then in this particular case this is not at all a valid situation as you can see here in this particular example we have created four buckets of same length that is two hence it is not at all valid remember only two buckets of the same length will be considered valid more than two will not be valid so you can see the next example in this particular example we have created two buckets of length two and then we have moved to length four so this is a valid example as you can see the rule is not getting violated so I hope this particular rule is clear and now by this we have covered all the six rules for forming a bucket so let's revise every bucket should contain at least a single one inside it the rightmost bit of the bucket should always start from one the length of the bucket will be equal to the number of ones inside it every bucket length should be in the powers of 2 and as we move from right to left the bucket length should always increase it should never decrease and the last rule says that no more than two buckets should have the same length so I hope the rules are clear to you all and with this rule let's take an example and solve the problem step by step so the question says that we need to First consider the following Stream So the stream contains the elements in this manner the stream goes like this it contains the bits zeros and ones and it is given that the total number of elements present inside this particular stream is 20. hence the variable n will be initiated with a value 20. now the question asks us to form the buckets for this particular stream so let's start so let's take this particular stream and let's try to form buckets as I said it is better to form buckets from the right hand side as the stream is going from right to left so first we can create a bucket of size one it is always recommended to start with a size 1. so the first bucket is of length 1 because it contains only a single one inside it and it is valid because it is a power of 2 that is 2 to the power 0. now if we move to the left we can see that we can create a bucket of the size 2 considering this bits 1 0 0 1 the right most element of this particular bucket is one hence the rule satisfies the length of this particular bucket is 2 and it is valid because it comes in the power of 2 that is 2 to the power 1. now if we move towards left we can take these four Once into a single bucket and since it contains four ones its size will be 4 and it is valid because it contains the right most element one as well as the size is a power of two and we are remained with the last bits which are again of size 4 so we can create a bucket of it so you can see we have considered all the rules and we haven't violated any of the rule also the rule that no more than two bucket sides should be of the same length is not violated now as you know that the stream is going from right to left so let's consider this scenario that the new bit 0 has got entered into the stream it will always enter from the right hand side so remember one thing whenever the new bit that has got entered into the stream is zero then in that case you don't have to do any changes in the Arrangements of the buckets because this algorithm is specially concerned for counting once inside this stream it is not bothered about the number of zeros that are entering into the streams hence whenever the new bit is zero we don't have to alter the arrangements of the buckets so I hope this is clear now let's say this zero bit that has got entered has now got old and let's say a new bit now enters into the stream now this time the bit is not zero it is 1 so whenever the new bit that has got entered into the stream is one then in that case you will have to alter the arrangements of buckets which means either you have to add the buckets or you need to alter the arrangements in this particular case you can see that there is only a one bucket which is having the length one the rule says that we can have two buckets of the same length but we cannot have more than two buckets of the same length here we already have a bucket one of length one so we can have one more bucket of length one which can accommodate this newly entered bit which is one so we can create a new bucket of length one and we can accommodate this new bit that has got entered and you can now see that we have successfully solved the problem of the newly entered one but what if now again a new bit one has got entered now in this particular situation you can clearly see that we already have two buckets of length one we cannot have one more bucket of length one because it will obviously violate the rule but if you look at the left side you can see that there is only a single bucket of length 2. we can still have one more bucket of length two because it is not going to violate the rule so what we can do is we can merge the two buckets of length 1 into a single bucket which will now be considered as a bucket of length 2. so the merging will go something like this you can see there are two buckets of length one we will take the bit from the first bucket of length 1 and the bit from the second bucket of length 1 and we can simply merge them while merging you will have to show this particular step that you are merging these two buckets so once we show this step we can simply merge this to buckets into a single so now you can see that there are two buckets of length two hence it is not going to violate the rule now we are still remained with the bit 1 we can simply form a bucket of length 1 and put that bit 1 inside that particular bucket and now you can see that we are having only one single bucket of length one so you can see the rules are not getting violated as well as we have formed all the buckets which contains all the elements properly according to the rule so I hope the bucket formation process is clear to you all so if you remember that this particular algorithm is specifically focused to count the number of ones in the given stream so now the question is asking us that we need to find the number of ones in in the recent 18 bits if you see the word recent it says that the place from where the new bits are entering that is from the right hand side so I have highlighted the 18 elements the most recent written elements from this particular stream and these are the elements so we need to count the number of ones from this particular recent 18 elements so in that case how this buckets are going to help us from this particular algorithm so now you don't have to do anything you just have to take the lens of the buckets that are coming under this recent 18 bits so you can see the first bucket of length 1 the second bucket is of length 2 the third bucket is again of length 2 so let's take those the fourth bucket is of length 4 and now the fourth bucket is the last bucket which is coming under this recent 18 bits so you can see that we have taken these four numbers which are the lengths of the buckets that are coming inside the recent 18 bits and now we just have to add them and we are now getting the answer as 9 so 9 is the number of ones which are coming under the recent 18 bits and that was the goal of this particular algorithm that is to find the number of ones in the given stream of data so you can see that there are Total Line bits of ones in the recent 18 bits so we have calculated it and I hope the datar geonis index Moto and algorithm is clear to you all if you guys have any single doubt you can simply put it in the comment section and also don't forget to post your reviews and suggestions because your one comment matters a lot for me and for more such videos you like share and subscribe to my channel also hit the Bell icon and don't forget to follow me on Instagram thanks a lot for watching have a good day ahead