# Consecutive 1's in Binary Numbers

# Consecutive 1's in Binary Numbers

AbhishekVermaIIT + 9 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]Kanahaiya + 1 comment saratchandraogi1 + 0 comments thank you very much

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

mukunda05holla + 2 comments Those who are looking for javascript solution

const n = parseInt(readLine(), 10); let count = 0; let result = 0; let arr = n.toString(2); for(let i = 0; i< arr.length; i++) { if(arr[i] == 0) { count = 0; } else { count++; result = Math.max(result, count) } } console.log(result)

shiza881 + 1 comment thankyou so very much for this. i was working with list and everybody here provides a solution with a binary number in an integer variable. thanks alot for help.

mukunda05holla + 0 comments glad i could

Kanahaiya + 0 comments hi

your solution is good but it can be optimize further. here is the trick to solve this problem in O(K).

priti_jha + 1 comment Stack stack=new Stack(); int count=1,i=-1,max=0; while(n!=0) { stack.push(n%2); n=n/2; } while(!stack.isEmpty()) { if(stack.peek()==i) { count++; }

`if(max<count) { max=count; } i=stack.peek(); if(i==0) { count=1; } stack.pop(); }`

bob_crosby5123 + 0 comments When we state real estate logos design, we mean a brand mark which has a capacity to impart in the interest of their business to the world. It's anything but a medium-term work for it requires a broad research work about the most recent real estate logo design patterns and contender's image imprint to think of something that is one of a kind, captivating and eye-getting.

Sort 79 Discussions, By:

Please Login in order to post a comment