AbhishekVermaIIT 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 [deleted]
srujan_madupu good logic...even i didn't get initially..is there any resourse to become STRONG in bit manipulation. thank you
AbhishekVermaIIT 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 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 Thanks a lot for appreciating the effort, makes it worth :)
Kj6995 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 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 oh thanks didn't read the question properly
anonymousGod @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 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 with221because13won't help much. Now, binary represention of221is11011101. Visualizing iterations ofwhile-loopusing 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) 0As the above example shows, number of consecutive
1's in n reduce by one in every iteration ofwhile-loop. Thus, counting the iterations, gives the required answer.anonymousGod I wasn't aware of such operation(n<<1) in java, have lot to learn. thanks again :)
Venkat30119 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 very well explained...thank you AbhishekVermaIIT
sahilsabarwal50 [deleted]
NagaNaresh superb logic man...
Sid_S [deleted]
pradeepyadava 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 great ! how did you come with it? i mean the what was the thought process behind framing the logic?plz do reply!
bannurahul321 bro i didnt get the usage of function !
paul_hunter007 use of function is to store biggest no. consecutive ones in result from count.
krobin_93 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 complexity of the soulution?
krobin_93 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 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 explain the logic
himamshu14 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 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 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 #!/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 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 not showing correct output for 439
[deleted] 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 [deleted]
souviksinharay 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