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]
Kanahaiya Here is the video explanation of the same-
Length Of The Longest Consecutive 1s In Binary Representation Of A Number | BitManipulation
saratchandraogi1 thank you very much
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
mukunda05holla 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 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 glad i could
Kanahaiya hi
your solution is good but it can be optimize further. here is the trick to solve this problem in O(K).
priti_jha 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 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