馃攳
Length Of The Longest Consecutive 1s In Binary Representation Of A Number | BitManipulation - YouTube
Channel: JAVAAID - Coding Interview Preparation
[2]
I'm gonna tell you the most efficient way
to count the maximum number of consecutive
[6]
1's in a binary string right now.
[14]
Hey, everyone, I am Kanahaiya Gupta.
[16]
Welcome to my youtube channel, let's start.
[21]
So, this is the given binary string, and in
that, we have different sequences of one.
[27]
The first sequence has number of 1's equals
to two.
[31]
And the second sequence has number of 1's
equals to three.
[35]
The third sequence has number of 1's equals
to four.
[39]
So, among all these, the answer is four, because
you need to return the maximum number of consecutive
[47]
1's, which is four.
[50]
this is the problem guys.
[53]
Now, we'll see how we are going to solve this
problem.
[58]
I have taken the number, which is 211184.
[62]
It is an integer number.
[65]
And this is a binary representation of this
number.
[70]
And these boxes represent the number of 1's
for each sequence.
[75]
So, I have highlighted with the same colour,
you can see, this sequence contains 1's two
[81]
times.
[82]
So, it shows the two, this second sequence
shows three 1's so, it鈥檚 represented by
[90]
three, and the third sequence having four
1's, is represented by four.
[96]
first will take this binary number.
[99]
and in the next step, we are going to calculate
the left shift of this binary number.
[105]
so will perform a left shift operation on
this number.
[109]
So, once you perform a left shift, this number,
so you can see, the whole string is shifted
[117]
by one.
[118]
And after that, if you will do AND operation
of both of these two, you will get this number.
[125]
So, you can see guys, in the initial string,
we have count of 1's two, in the second sequence
[133]
has three and the third sequence has four.
[136]
but after performing this operation, the first
sequence has one, second sequences have two
[143]
and the third sequence has three.
[145]
So, in each sequence, it's reduced by one.
[149]
And the same is update over here.
[152]
So, after applying this operation, each sequence
is reduced by one.
[160]
so now perform the same step again, this time
number will be this.
[168]
And we have calculated the left shift, and
again perform the end operation.
[174]
After this AND operation, again, we can see
each sequence is reduced by one, the same
[180]
is updated over here.
[182]
So, like that, if you perform the same operation,
again and again, we can see Finally, all becomes
[191]
zero.
[192]
So now we don't need to perform this operation
anymore.
[196]
Because there's no 1's if you perform this
operation, it doesn't make any sense, we have
[202]
to perform this operation till we get zero.
[208]
And each step is a counter.
[211]
Because of every step we are reducing one
from every sequence if we have four ones.
[219]
So, you can see, there will be four steps
because this is the maximum number of 1's
[225]
and this one will be there till the end.
[229]
If you see the steps, like we have two 1's,
right.
[233]
So, after two-step, this will not be there.
[236]
So, the first step, it reduced to one.
[238]
And the second step, after performing the
second step it's gone.
[243]
So, like that, this sequence has three 1's.
[247]
So, once you perform one step, so it reduced
to two, then you perform the next step, it
[252]
reduced to one.
[253]
And after this three-step, it's no more.
[256]
so, like that.
[257]
So, the longer sequence will stick up till
the end.
[265]
And we have to calculate the length of the
longest sequence or you can see we have to
[269]
calculate the maximum number of 1's.
[271]
So, it's nothing.
[272]
it's the same thing, just counting the steps.
[275]
Or you can say instead of steps, you can say
it's a count.
[279]
So, for each step, we are maintaining the
count and increasing that.
[283]
So, till the end, once it's zero, we'll see
how many steps and count are there four.
[289]
So, it means four is the answer.
[295]
I hope that's clear to you.
[296]
Let's see how we are going to write the logic
for it.
[301]
so, this is the, method guys count consecutive
once in a binary.
[305]
In that, I'm assuming we'll get the integer
number.
[309]
Once you get into the number, I am just taking
a variable count, which will hold the count
[315]
of the maximum conservative ones.
[318]
And this is a while loop.
and this while loop will keep on running until
[323]
the number is greater than zero.
[326]
So just know you've seen we have to perform
those steps until the number is greater than zero.
[333]
Once it's zero, we will stop.
[337]
And the main step which we are going to perform
is this, will take the number and after that,
[342]
we'll do the AND operation of the number with
the left shit.
[347]
and whatever the result will come will store
into a number and this number is updated with
[352]
the new result.
[353]
in the same operation we have to keep on follow
until the number is greater than zero and
[359]
each step, we will count how many steps have
been performed.
[364]
for that, we are maintaining count and we
keep on increasing this count, based on those
[371]
steps, how many steps have been done.
and this count represents the number of consecutive
[376]
1's as we have already discussed, because
the longest the length of the one or you can
[384]
see the longest the length of the sequence
of 1's, the counter will keep on incrementing
[391]
and it will hold the number of 1's and after
that we can return the count.
[398]
let's try to analyse this algorithm guys.
[400]
So, this is the same example which we have
seen.
[406]
so, in that we know everything here, it depends
on the number of 1's.
[413]
But among all sequences, it depends on the
number of maximum numbers of 1's.
[419]
If there are four consecutive 1's, we are
going to perform four steps because, after
[427]
the fourth step, everything will be zero.
[430]
And the steps you can see only that green
consecutive 1's exist till the end.
[437]
Because this is the longest string or longest
consecutive 1's, inside the string.
[444]
So, the total number of count is directly
proportional to the longest string or we can
[453]
say the total number of count is directly
proportional to the longest consecutive sequence.
[459]
So, based on that, we can easily say the time
complexity of this algorithm is O(K).
[468]
We're K is the length of maximum consecutive
1's and the space complexity is O (1) because
[474]
we have not used any extra space over here.
[477]
I hope guys, that this problem is clear to
you.
[479]
and this question has been asked in many interviews,
as well as is also given in a hackerrank platform.
[485]
So, you can go and try this question on hackerrank
also.
[489]
If you have any problem in solving this.
[491]
you can check out my source code which is
present in the git hub and let me know how
[495]
many marks you got in a hackerrank platform
solving this.
[499]
Thanks for watching guys.
Most Recent Videos:
You can go back to the homepage right here: Homepage