Problem

Submissions

Hints & solutions

Discuss

Binary Gap

Easy

0/40

Average time to solve is 15m

Contributed by

4 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

1
7

Sample Output 1:

Explanation For Sample Input 1:

In the first test case, the binary representation of 7 is “111”. The max distance between the first and second bit or the second and third bit is 1. Hence the answer is 1.

Sample Input 2:

2
5
11

Sample Output 2:

2
2

Explanation For Sample Input 2:

For test case 1, The binary representation of 5 is “101”. The max distance between the first and last bit is 2. 
Hence the answer is 2.

For test case 2, The binary representation of 11 is “1011”. The max distance between the first and third bit(1 based indexing) is 2, between the third and fourth bit, is 1. 
Hence the answer is 2.

Hint 1

Hint 2

Can you think of a brute force approach?

Approaches (2)

Approach 1

Approach 2

Intuitive Approach

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.

Time Complexity

O(log(N)), where N is the number given to you.

We just need to traverse the bits of the number which can be done in O(log(N)).

Space Complexity

O(log(N)), where N is the number given to you.

In the worst case, when all the bits of the number is set, then the size of our vector store will be log(N). Hence the space complexity is O(log(N)).

(100% EXP penalty)

Binary Gap

Console