We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Tutorials
  3. LinkedIn Placements
  4. Consecutive 1's in Binary Numbers
  5. Discussions

Consecutive 1's in Binary Numbers

Sort 75 Discussions, By:

votes

  • 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 with 221 because 13 won't help much. Now, binary represention of 221 is 11011101. Visualizing iterations of while-loop using binary clarifies the procedure :

        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 1's in n reduce by one in every iteration of while-loop. Thus, counting the iterations, gives the required answer.

        • 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 + 0 comments

      Here is the video explanation of the same-

      Length Of The Longest Consecutive 1s In Binary Representation Of A Number | BitManipulation

  • 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

  • Kanahaiya + 0 comments

    Length Of The Longest Consecutive 1s In Binary Representation Of A Number | BitManipulation

    Click here for video explanation

    Would really appreciate your feedback like, dislike , comment etc. on my video.

  • sahnigwl + 1 comment
    binary=list(map(int,bin(int(input())).replace('b','')))
print(binary)
result = 0
maximum = 0
for i in binary:
    if i==1:
        result += 1
        if result > maximum:
            maximum = result

    else:
        result = 0
print(maximum)
    • sahnigwl + 0 comments

      python code for the question

  • 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 + 1 comment
    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.

    • Kanahaiya + 0 comments

      Here you are making c to zero if sequenc is something 1000.

      Here is the efficient way to solve this problem. https://youtu.be/bc7cxeDy308

  • 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] + 2 comments
    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]
    • Kanahaiya + 0 comments

      Here is the efficient way to solve this problem.

      https://youtu.be/bc7cxeDy308

Load more conversations