Flip Bit to Win

Easy
0/40
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in companies
HSBCAmazonMicrosoft

Problem statement

Ninjas are often known for their stealth execution and accuracy to get the job done right. While honing their art of moving through dense forests stealthily, they need the maximum number of continuous trees one after the other for practicing.

Trees are represented by 1s and empty places by 0s (basically a binary representation of a given integer). You are also given an extra tree which you can plant at any empty place (i.e. you can flip one of the zeroes in the binary representation to 1). The tree should be planted such that the maximum number of consecutive trees is maximized.

Your task is to report the maximum number of consecutive trees after plantation.

Note:

You may also choose not to plant that extra tree at all.
For Example: 
Input: 54
Output: 5

The binary representation of 54 is 110110.
After flipping the third bit from the left, we get consecutive 5 bits. i.e. 111110.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the 'T' test cases are as follows.

The first and the only line of each test contains an integer 'N', denoting the integer whose consecutive ones in the binary representation are to be found out.
Output format: 
For the integer, print the length of the longest sequence of 1 s you could create by flipping exactly one bit. 

Output for 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 <= 1000
2 <= N <= 10^9

Where 'N' is the integer that is to be looked into for the maximum consecutive ones after flipping 1 bit.

Time limit: 1 second
Sample Input 1:
3
1775         
12         
15
Sample Output 1:
8
3
4
4
Explanation For Sample Input 1:
For first test case:
The binary representation of 1775 is 11011101111.
After flipping the highlighted bit, we get consecutive 8 bits. (11011111111)

For second test case:
The binary representation of 12 is 1100.
After flipping the highlighted bit, we get consecutive 3 bits. (1110)

For third test case:
The binary representation of 15 is 1111.
There is no need to flip bits here since all bits are ones.
Sample Input 2:
2
71
54
Sample Output 2:
4
5
Explanation For Sample Input 2:
For first test case:
The binary representation of 71 is 1000111.
After flipping the 4th bit, we get consecutive 4 bits.

For second test case:
The binary representation of 54 is 110110.
After flipping the 3rd bit, we get consecutive 5 bits.
Hint

Count number of ones around every 0 bit.

Approaches (2)
Brute Force Approach

Approach: The idea is to count a number of ones on both sides of each zero. The required index is the index of zero having a maximum number of ones around it. Following variables are used in implementation:

 

Steps:

  1. First, count the total number of zeros and ones present in the binary representation of the number ‘N’.
    • If the total number of zeros is 0 then the longest consecutive number of ones present in the representation is the total length of the binary number.
    • If the total number of ones is 0 then the longest consecutive number of ones present in the representation is 1 (since you can get at most a single one by flipping any of the zeros once).
  2. Now iterate over the length of the binary representation of the number (length N) and check:
  3. For every 0, count the number of 1s on both sides of it.
    • Start from the position of zero bit and keep moving towards left until another zero bit is reached or the end of the number is reached, keep incrementing the count of the number of ones present on the left side of the zero bit.
    • Now start moving towards the right until another zero bit is reached or the end of the number is reached, keep incrementing the count of the number of ones present on the right side of zero bit.
    • Add both of the counts and also an extra one (since the zero bit which would be flipped should also be counted).
  4. Check for every zero bit encountered if the present count of consecutive ones is greater than the maximum count of consecutive ones obtained till now, update the
  5. ‘MAXIMUMCONSECUTIVEONECOUNT = ’PRESENTCOUNT , if it is greater.
  6. We finally return ‘MAXIMUMCONSECUTIVEONECOUNT’.
Time Complexity

O(logN), where ‘N’ is the given integer.

 

Since every index will be visited at most twice the time complexity will be O(logN).

Space Complexity

O(logN), where ‘N’ is the given integer.

 

As a string was used for binary representation of given number.

Code Solution
(100% EXP penalty)
Flip Bit to Win
Full screen
Console