# Consecutive 1's in Binary Numbers

# Consecutive 1's in Binary Numbers

AbhishekVermaIIT + 8 comments The problem can be solved most efficiently using bit-manipulation. Once again the editorial disappointed me. "Discussions" has better solutions than the editorial. Anyways, the problem can be solved in

**O(b)**complexity, where**b=consecutive 1's**:n = int(input()) ans = 0 while n>0 : n &= (n<<1) ans += 1 print(ans)

**Logic :**"Logical-and" accompanied with "left-shift" reduces consecutive set-bits(1's) by 1. Thus, counting these operations gives the required answer.

nitinshk1111 + 0 comments [deleted]srujan_madupu + 1 comment good logic...even i didn't get initially..is there any resourse to become STRONG in bit manipulation. thank you

AbhishekVermaIIT + 0 comments I can't comment about resource in particular. Though, HackerRank has an entire subdomain dedicated to Bit-manipulation. You can start practicing there. At times, I have found awesome posts in discussions. Start reading them, a lot can be learnt from there.

werner + 1 comment Abhishek your solutions makes me feel like i have lot to do in programming and they r helping me to push a little bit in acquiring programming knowledge.thank you

AbhishekVermaIIT + 0 comments Thanks a lot for appreciating the effort, makes it worth :)

Kj6995 + 1 comment i tried using the n &= (n-1) but this doesn't seem to work...can anyone please tell me why? it does the same as mentioned in this

AbhishekVermaIIT + 1 comment There's slight difference. The mentioned

`n &= (n-1)`

operation actually counts**total**set-bits. This problem requires**maximum consecutive**set-bits.

Example :For binary

`1110011`

, the number of set-bits are 5 (this will be result of the mentioned operation). But, the required answer would be 3, since maximum number of consecutive set-bits are 3.Kj6995 + 0 comments oh thanks didn't read the question properly

anonymousGod + 1 comment @AbhishekVermaIIT Hey, coming from java I'm not able to get what are you trying to do with

*n &= (n<<1)*and your logic of "left-shift". Can you plese explain with a small example, say 13? Thank you very much.AbhishekVermaIIT + 3 comments Other than I/O, all operations stay as it is, in Java. Here's Java version for you :

public static void main(String[] args) { Scanner scan = new Scanner(System.in) ; int n = scan.nextInt() ; scan.close() ; int ans = 0 ; while (n > 0) { n &= (n<<1) ; ans += 1 ; } System.out.println(ans) ; }

Since you want explanation with an example, I'll explain it withbecause`221`

won't help much. Now, binary represention of`13`

is`221`

. Visualizing iterations of`11011101`

using binary clarifies the procedure :`while-loop`

`First Iteration : n 11011101 n<<1 110111010 n & (n<<1) 10011000 Second Iteration : n 10011000 n<<1 100110000 n & (n<<1) 10000 Third Iteration : n 10000 n<<1 100000 n & (n<<1) 0`

As the above example shows, number of consecutive

's in`1`

**n**reduce by one in every iteration of. Thus, counting the iterations, gives the required answer.`while-loop`

anonymousGod + 0 comments I wasn't aware of such operation(n<<1) in java, have lot to learn. thanks again :)

Venkat30119 + 0 comments Bro small dobut but with out Dividing how we can get that bits...In ur program their is no (n%2) and etc...can u clarify it plz!!!

d_shubham777 + 0 comments very well explained...thank you AbhishekVermaIIT

sahilsabarwal50 + 0 comments [deleted]NagaNaresh + 0 comments superb logic man...

Sid_S + 0 comments [deleted]

pradeepyadava + 3 comments public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int count=0; int result=0; while(n!=0) { if(n%2==1) { count++; result=fun(count,result); } else { result=fun(count,result); count=0; } n=n/2; } System.out.println(result); } public static int fun(int a,int b) { if(b<a) b=a; return b; } }

raghav_rao + 1 comment great ! how did you come with it? i mean the what was the thought process behind framing the logic?plz do reply!

bannurahul321 + 1 comment bro i didnt get the usage of function !

paul_hunter007 + 0 comments use of function is to store biggest no. consecutive ones in result from count.

krobin_93 + 2 comments This one is more optimized solution. There is no need to compare count and result(max in my solution) for every iteration of while loop. Hope it helps.

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int max=0,count=0; while(n>0){ if(n%2==1){ count++; }else{ max=Math.max(count,max); count=0; } n=n>>1; // same as n=n/2 } System.out.println(Math.max(count,max)); } }

bhuvanms + 0 comments complexity of the soulution?

krobin_93 + 1 comment Since we are checking every bit of the integer, the time complexity will be O(k) where k is the number of bits/digits in the binary representation of the number n. Hope I am clear.

AbhishekVermaIIT + 0 comments It's good to see comments like these. I was reluctant to write post for this problem, but your comment convinced me to write it finally. Have a look at

**this**if you find it helpful.

jayu24 + 0 comments explain the logic

himamshu14 + 0 comments num=13 s=str(bin(num)) c=0 for i in range(len(s)): if s[i]=='1' and str[i]==str[i+1]: c=c+1

print(c)

it is showing error though the logic is correct. can someone pls explain why

himamshu14 + 0 comments num=13 s=str(bin(num)) print(s) c=0 for i in range(len(s)): if s[i]=='1' and str[i]==str[i+1]: c=c+1

print(c)

it is showing error though the logic is correct. can someone pls explain why

muskan210497 + 0 comments int main(){ int n, r,c; cin >> n; while(n!=0){ r = n%2; n = n/2; if(r ==1){ c +=1; } else if(r ==0){ c = 0; } } cout<< c; return 0; }

can anyone tell me what is the problem in my code. Test case 2 is not satisfying.

udaykiran_kondr1 + 0 comments #!/bin/python3 import sys import math n = int(input().strip()) k=int(math.log(n,2))+1 j=0 c=0 l=[] while(j<k): if(n & 1<<j): c+=1 else: l.append(c) c=0 j+=1 l.append(c) print(max(l))

abhishek008 + 1 comment passing all test case except #testcase2.

int main() {

`int n; int rem; int count=0; scanf("%d",&n); while(n!=0) { rem=n%2; n=n/2; if(rem==1) count=count+1; else if(rem==0) count=0; } printf("%d",count); return 0; }`

aakankshasahu09 + 0 comments not showing correct output for 439

[deleted] + 1 comment int n; cin >> n; int count=0,pre=0; while(n!=0) { if(n%2) count++; else { if(count>pre) pre=count; count=0; } n/=2; } if(count>pre) pre=count; cout<<pre;

abhilashpani651 + 0 comments [deleted]

souviksinharay + 0 comments Scanner in = new Scanner(System.in); int n = in.nextInt() , divisor = n , count = 0 , max = 0 , power = -1; while(true) { if(divisor % 2 == 0) { if(count > max) max = count; if(divisor == 0) break; power = -1; count = 0; } else{ count ++; } divisor = divisor / 2; } System.out.println(max);

Sort 74 Discussions, By:

Please Login in order to post a comment