1-bit and 2-bit Characters

🏠 ⬅️ ➡️

We have two special characters:

  • The first character can be represented by one bit 0.
  • The second character can be represented by two bits (10 or 11).

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

Example 1:

Input: bits = [1,0,0] Output: true Explanation: The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.

Example 2:

Input: bits = [1,1,1,0] Output: false Explanation: The only way to decode it is two-bit character and two-bit character. So the last character is not one-bit character.

Constraints:

  • 1 <= bits.length <= 1000
  • bits[i] is either 0 or 1.
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, n
    logical :: ans
    character(len=100) :: input_string

    ! Example 1
    write(*,*) "Example 1"
    input_string = "[1,0,0]"
    read(input_string, *) n, (ans, i=1,n)
    call solve(n, ans)

    ! Example 2
    write(*,*) "Example 2"
    input_string = "[1,1,1,0]"
    read(input_string, *) n, (ans, i=1,n)
    call solve(n, ans)

contains

subroutine solve(n, ans)
    implicit none
    integer, intent(in) :: n
    logical, intent(out) :: ans

    integer :: i
    logical :: last_is_one

    last_is_one = .false.
    do i = 1, n - 1
        if (ans(i)) then
            last_is_one = .not. last_is_one
        end if
    end do

    if (last_is_one) then
        ans = .true.
    else
        ans = .false.
    end if
end subroutine solve

end program main
✅ Compiled
✅ Executed
⚠️ Correct 
module one_bit_character

implicit none

contains

function solve(bits) result(output)

integer, intent(in) :: bits(:)
logical :: output

integer :: i, n

n = size(bits)

if (n == 1) then

output = .true.

else

output = .false.

do i = 1, n - 1

if (bits(i) == 1) then

output = .true.

exit

end if

end do

end if

end function solve

end module one_bit_character

program main

use one_bit_character

implicit none

integer, parameter :: n = 3
integer :: bits(n) = [1, 0, 0]

write (*, *) solve(bits)

end program main
🌐 Data from online sources 
def is_one_bit_character(bits):
    i = 0
    while i < len(bits) - 1:
        i += bits[i] + 1
    return i == len(bits) - 1

The algorithm iterates through the binary array bits. If the current element is 1, the next character will be a 2-bit character, so the index i will be incremented by 2 (1 from the current iteration and 1 from the 2-bit character). If the current element is 0, it means that the current character is a 1-bit character, so the index i is incremented by 1 (from the current iteration). The loop ends either when reaching the last character or when going beyond it.

After the loop, if i is equal to the last index of the array (i.e., bits.size() - 1, bits.length - 1, or len(bits) - 1 depending on the language), it means the last character is a 1-bit character, and the function returns true. Otherwise, it returns false.

🌐 Data from online sources 
bool isOneBitCharacter(std::vector<int>& bits) {
    int i;
    for (i = 0; i < bits.size() - 1; i++) {
        i += bits[i];
    }
    return i == bits.size() - 1;
}

The algorithm iterates through the binary array bits. If the current element is 1, the next character will be a 2-bit character, so the index i will be incremented by 2 (1 from the current iteration and 1 from the 2-bit character). If the current element is 0, it means that the current character is a 1-bit character, so the index i is incremented by 1 (from the current iteration). The loop ends either when reaching the last character or when going beyond it.

After the loop, if i is equal to the last index of the array (i.e., bits.size() - 1, bits.length - 1, or len(bits) - 1 depending on the language), it means the last character is a 1-bit character, and the function returns true. Otherwise, it returns false.