Time Complexity = O(1) = order of number of bits i.e, log(m or n = range indices). O(Number of bits to represent Integer), but will be much less than that in amortized case. Space Complexity = O(1) Please share your solutions which worked for you in the comments section below.

@TheArbaaz-rn2tq

4 жыл бұрын

can you cleare the time complexity O(1) or O(log n)?

@KnowledgeCenter

4 жыл бұрын

m, n = 1st and last numbers of range. Number of bits in m = 1 + floor( log(m) ) Number of bits in n = 1 + floor( log(n) ) So, take max of these. So, O(log(n)). We can say it as constant, since we are using integers. And Maximum bits used by integers can be typically 32 or 64. So, it boils down to O(32) or O(64) or O(1). Better way would be O(B), where B = number of bits.

@joeybaruch1933

4 жыл бұрын

Time complexity is a function of the size of the input. If you look at the input in this question, it is two numbers - the size of which are the number of bits in their bit representation. Therefore, this solution is linear time or O(|input|)

Good one! I just added a precheck in my solution for counting the bits in the numbers and if not same, return 0: int bitsInM = (int) (Math.log(m) / Math.log(2) + 1); int bitsInN = (int) (Math.log(n) / Math.log(2) + 1); if (bitsInM != bitsInN) return 0;

You are awesome. Perfect explanation. Keep doing the knowledge sharing. 👍

@KnowledgeCenter

4 жыл бұрын

Thank you.

Thank you so much!!!

@KnowledgeCenter

3 жыл бұрын

Happy to help.

Just noticed that the AND will always result into an Even number.

@KnowledgeCenter

4 жыл бұрын

For majority of cases you are correct except a case when m = n and m is Odd. In this case there is just 1 number in range. So, result will be that number itself. So, if m odd it will be odd. In other cases i.e., m < n, we have more than 1 number in range. So, least significant bit will flip after every number. So, AND of LSB =0 . Hence Even, as you are saying.

@Knowledge Center why did you stop making leetcode videos?

Very nice explanation sir..

@KnowledgeCenter

4 жыл бұрын

Thanks.

great ...., can you plz bring out explanation of advanced topics such as Mo's tree , square root approach , sparse , segment .... KZread really lacks good explanation on these.... How these can be used efficiently and easily...

@KnowledgeCenter

4 жыл бұрын

Thanks. I will try to add these topics soon.

Very good explanation! Sir, how to develop the thinking?My sln was to loop through and do the and operation with all digits. I dnt think so I could have come with this sln.

@KnowledgeCenter

4 жыл бұрын

For bit-operations based questions, I would say the best way is start with examples and write down bit representations of numbers, and try to find pattern there. Example always helps. It may take time, but in an interview situation interviewer is there to guide you whether you are heading in right direction or not. Practice matters. Also this question has a good level. So, don't worry too much if didn't reach out optimal solution in first go. Good luck.

@rajeshpatel-lg8zp

4 жыл бұрын

@@KnowledgeCenter Thank you

Thanks a lot for such a nice explanation sir ! I have a doubt sir, as explained by you, we were doing these shifts in binary represetations , but then while writing code why did we do in decimal numbers itself and did not change it to binary first ?

@KnowledgeCenter

4 жыл бұрын

Left/Right shifts are considered binary operations, just like &(AND), |(OR), and ^(XOR). So, x = 1234 >> 1. Here we did binary right-shift on 1234. So, x will not shift the decimal 1234 by 1 digit, but it will shift 1 binary bit in the representation of 1234. So, x does not become 123, but instead its 617.

@vrindakakkar8752

4 жыл бұрын

@@KnowledgeCenter Okay sir, thanks a lot.