Introduction

In this blog post, we will explore how to solve the LeetCode problem "868" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 <= 109

Explanation

Here's the breakdown of the solution:

• Iterate through bits: Examine each bit of the integer from right to left using bitwise operations.
• Track last 1 position: Keep track of the position of the most recently encountered '1'.

• Calculate and update max distance: When a new '1' is found, compute the distance to the previous '1', and update the maximum distance encountered so far.

• Runtime Complexity: O(log n), where n is the input number. This is because the number of iterations is proportional to the number of bits in n, which is log base 2 of n.

• Storage Complexity: O(1), as we are only using a few integer variables.

Code

    def binaryGap(n: int) -> int:
    """
    Finds 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.
    """
    last_one = -1  # Initialize to -1 to indicate no previous 1
    max_distance = 0
    position = 0

    while n > 0:
        if n % 2 == 1:  # Check if the current bit is 1
            if last_one != -1:
                distance = position - last_one
                max_distance = max(max_distance, distance)
            last_one = position
        position += 1
        n //= 2  # Right-shift to examine the next bit

    return max_distance