Is Binary Gap easy or hard?

Binary Gap is classified as an Easy problem. The challenge mainly involves understanding binary representation and tracking the distance between consecutive 1 bits. It is commonly used to introduce bit manipulation concepts.

Binary Gap Python/Java solution

In Python, convert using bin(n) or iterate with bit operations while shifting the number. In Java, use Integer.toBinaryString(n) for the string approach or bitwise operations like (n & 1) and n >>= 1. Both implementations run in O(log n) time.

How to solve Binary Gap in O(log n)?

Process the binary representation one bit at a time. Maintain the position of the previous 1 bit, and whenever another 1 appears, compute the distance between indices. Update the maximum gap and continue shifting the number right until all bits are processed.

What is the best approach for Binary Gap?

The most efficient approach iterates through the bits of the number using bit manipulation. Check each bit with n & 1 and shift the number right using n >> 1 while tracking the index of the last seen 1. This runs in O(log n) time and O(1) space because the loop processes each bit once without creating extra data structures.

Is Binary Gap asked at Google/Amazon/Meta?

Binary Gap is typically categorized as an easy bit manipulation problem and appears in screening rounds or practice sets rather than deep system interviews. Similar bit scanning and binary representation problems do appear at companies like Amazon and Google for early-stage coding rounds.

What data structure is used in Binary Gap?

No complex data structure is required. The optimal approach relies on bit manipulation with simple integer variables to track bit positions. An alternative implementation may use a string representation of the binary number.

What is the time complexity of Binary Gap?

The time complexity is O(log n) because the algorithm processes one bit per iteration and an integer has log2(n) bits. Both the bit manipulation approach and the binary string approach have the same time complexity, though the string version uses additional memory.

Description Solution Video 15:42

868. Binary Gap

Easy74.2% acceptance6 companies

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Constraints:

1 <= n <= 10⁹

Asked at 6 companies

Twitter eBay Microsoft

Google Amazon Bloomberg

Topics

Bit Manipulation

15:42

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def binaryGap(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution