Last Updated: 17 Apr, 2021
Binary Gap
Easy
Asked in company
It is a day of celebration here at Coding Ninjas because our beloved Ninja Hu-chan is going to get his JatSu belt (the highest belt a ninja can get). He is just one step away from making his dream come true, but hold the line, Hu-chan’s master knows all his weaknesses and is going to do a final test of his skills before he is announced as the greatest ninja ever.
Master is aware of Ninja Hu-chan’s rivalry with maths and therefore he gives him a mathematical problem to solve, being a good friend and well-wisher of our Ninja, can you help him solve the problem assigned and thus acclaim the title of the greatest ninja?
The problem read as follows:
You are given a number ‘NUM’, return the maximum distance between any two adjacent 1s in the binary representation of 'NUM'.
Note:
The two 1s are called adjacent if there isn’t another 1 between them. The distance between 2 bits is the absolute difference between their bit positions.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow.
The first line of each test case contains a single positive integer, ‘NUM’.
Output Format:
For each test case, print the maximum distance between any two adjacent 1s in the binary representation of ‘NUM’.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘NUM’ <= 10^8
Where ‘T’ is the number of test cases and ‘NUM’ is the given number.
Time Limit: 1sec
Approaches
- Let the current number be ‘NUM’. We know how to find the binary representation of any number: By repetitively dividing it by 2 and checking if the current bit(NUM&1) is 1 or not.
- If the current bit is 1, store the index in a vector named 'STORE".
- For example if our number is ‘NUM’ = 11, then ‘STORE’ is = {0,1,3}.
- The task becomes very simple here, we just need to return the maximum difference between any two adjacent values in the vector ‘STORE’. Here it is equal to the difference between the second and third values, 3-1 = 2.
- In the previous approach after finding all the indices, we were comparing only adjacent elements in ‘STORE’.
- Therefore for any set index ‘IDX’, only the index preceding it and only the index following it matters, not the whole vector.
- Keep a variable ‘LAST’ which will store the last index where the bit was set. Also, keep a variable ‘ANS’ which will store our answer. Initially ‘LAST’ = num(any high value) and ‘ANS’ = 0.
- Traverse the number bitwise. With every traversal increment an index variable ‘IDX’ by 1. Initially ‘IDX’ = 0.
- Whenever you encounter a set bit, update ‘ANS’ to be maximum of ('ANS', ‘IDX’ - ‘LAST’) and update ‘LAST’ as ‘LAST’ = ‘IDX’.
- Return the value of ‘ANS’ at the end.
Similar problems
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Pair Product Div by K
Moderate
Posted: 15 May, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Merge Two Sorted Arrays Without Extra Space
Moderate
Posted: 19 Nov, 2022
Co-Prime
Hard
Posted: 14 Dec, 2022
First Digit One
Moderate
Posted: 14 Oct, 2025
Special Digit Numbers
Hard
Posted: 31 Oct, 2025