Binary Gap

🏠 ⬅️ ➡️

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
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program longest_ones_distance
    implicit none

    integer :: n, i, j, dist, max_dist
    logical :: found
    character(len=64) :: bin_str

    do while (.true.)
        read(*,*) n
        if (n == -1) exit

        write(bin_str, '(Z0)') n
        max_dist = 0
        found = .false.
        do i = 1, len(trim(bin_str))-1
            if (bin_str(i:i+1) == '11') then
                found = .true.
                dist = abs(i - (i + 1))
                if (dist > max_dist) then
                    max_dist = dist
                end if
            end if
        end do

        if (found) then
            print *, max_dist
        else
            print *, 0
        end if
    end do
end program longest_ones_distance
✅ Compiled
❌ Executed
❌ Correct 
! Declare variables
integer :: n, i, j, longest_distance, current_distance
logical :: found_adjacent_ones

! Read input
read(*,*) n

! Initialize variables
longest_distance = 0
found_adjacent_ones = .false.

! Convert n to binary
do i = 1, 32
    if (mod(n, 2) == 1) then
        if (found_adjacent_ones) then
            current_distance = i - j
            if (current_distance > longest_distance) then
                longest_distance = current_distance
            end if
        else
            found_adjacent_ones = .true.
            j = i
        end if
    end if
    n = n / 2
end do

! Output result
write(*,*) longest_distance

end
🌐 Data from online sources 
def push_dominoes(dominoes: str) -> str:
    prev, cur = None, dominoes
    while prev != cur:
        prev = cur
        cur_lst = list(prev)
        for i in range(len(cur)):
            if prev[i] == 'L' and i > 0 and prev[i - 1] == '.':
                cur_lst[i - 1] = 'L'
            elif prev[i] == 'R' and i < len(cur) - 1 and prev[i + 1] == '.':
                cur_lst[i + 1] = 'R'
        cur = ''.join(cur_lst)
    return cur
  1. Initialize prev and cur variables to store the state of dominoes. Set cur initially to the input string.
  2. Run a loop until the states of dominoes do not change, i.e., prev != cur.
  3. Iterate through each character in the prev string:
  4. If the character is 'L' and there is a domino to its left, and the left domino is '.', set that domino to 'L'.
  5. If the character is 'R' and there is a domino to its right, and the right domino is '.', set that domino to 'R'.
  6. Concatenate the new state of the dominoes to form the string cur.
  7. Continue the loop until there is no change in the states of the dominoes.
  8. Return the final state of the dominoes as a string.
🌐 Data from online sources 
#include <string>
using namespace std;

string pushDominoes(string dominoes) {
    int n = dominoes.size();
    string prev, cur = dominoes;
    do {
        prev = cur;
        for (int i = 0; i < n; ++i) {
            if (prev[i] == 'L' && i > 0 && prev[i - 1] == '.')
                cur[i - 1] = 'L';
            else if (prev[i] == 'R' && i < n - 1 && prev[i + 1] == '.')
                cur[i + 1] = 'R';
        }
    } while (prev != cur);
    return cur;
}
  1. Initialize prev and cur variables to store the state of dominoes. Set cur initially to the input string.
  2. Run a loop until the states of dominoes do not change, i.e., prev != cur.
  3. Iterate through each character in the prev string:
  4. If the character is 'L' and there is a domino to its left, and the left domino is '.', set that domino to 'L'.
  5. If the character is 'R' and there is a domino to its right, and the right domino is '.', set that domino to 'R'.
  6. Concatenate the new state of the dominoes to form the string cur.
  7. Continue the loop until there is no change in the states of the dominoes.
  8. Return the final state of the dominoes as a string.