Convert Binary Number in a Linked List to Integer

🏠 ⬅️ ➡️

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit is at the head of the linked list.

Example 1:

Input: head = [1,0,1] Output: 5 Explanation: (101) in base 2 = (5) in base 10

Example 2:

Input: head = [0] Output: 0

Constraints:

  • The Linked List is not empty.
  • Number of nodes will not exceed 30.
  • Each node's value is either 0 or 1.
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    ! Solves the problem described in the comment block
    implicit none

    type :: Node
        integer :: value
        type(Node), pointer :: next => null()
    end type

    type(Node), pointer :: head => null(), current => null()
    integer :: i, n, dec_val

    ! Read input
    read(*,*) n
    allocate(head)
    head%value = 0
    do i=2,n+1
        allocate(current)
        current%value = 0
        if (i <= n) then
            read(*,*) current%value
        end if
        current%next => head
        head => current
    end do

    ! Solve problem
    dec_val = solve(head)

    ! Output result
    write(*,*) dec_val

contains

    function solve(head) result(dec_val)
        implicit none
        type(Node), pointer :: head
        integer :: dec_val

        dec_val = 0
        do while (associated(head))
            dec_val = dec_val * 2 + head%value
            head => head%next
        end do
    end function

end program
❌ Compiled
❌ Executed
❌ Correct 
module problem_172

implicit none

type :: node
    integer :: value
    type(node), pointer :: next => null()
end type

interface
    function solve(head) result(result)
        type(node), pointer :: head
        integer :: result
    end function
end interface

contains

function solve(head) result(result)
    type(node), pointer :: head
    integer :: result, value

    ! Initialize the result to 0
    result = 0

    ! Loop through the linked list
    do while (associated(head))
        ! Get the value of the current node
        value = head%value

        ! Shift the result to the left by 1 bit
        result = result * 2

        ! Add the value of the current node to the result
        result = result + value

        ! Move to the next node
        head => head%next
    end do

end function

end module

program main
    use problem_172
    implicit none
    type(node), pointer :: head
    integer :: result

    ! Create a linked list with the binary representation of the number 5
    head => null()
    allocate(head%next)
    head%next%value = 1
    allocate(head%next%next)
    head%next%next%value = 0
    allocate(head%next%next%next)
    head%next%next%next%value = 1

    ! Solve the problem
    result = solve(head)

    ! Print the result
    write (*,*) "The decimal value of the linked list is: ", result

    ! Create a linked list with the binary representation of the number 0
    head => null()
    allocate(head%next)
    head%next%value = 0

    ! Solve the problem
    result = solve(head)

    ! Print the result
    write (*,*) "The decimal value of the linked list is: ", result

end program
🌐 Data from online sources 
def min_operations(arr1, arr2):
    n = len(arr1)
    dp = [float('inf')] * n
    for a in arr2:
        new_dp = [float('inf')] * n
        p = 0
        for i in range(n):
            if a < arr1[i]:
                new_dp[i] = p
            if i > 0 and dp[i - 1] < p:
                p = dp[i - 1]
            if arr1[i] > arr1[i + 1]:
                return -1
        dp = new_dp
    return dp[-1]
  1. Initialize a dp array with the same length as arr1, fill it with infinity.
  2. Loop through each element in arr2 (as a).
  3. At each iteration, create a new dp array called new_dp.
  4. Use a variable p to track the minimum number of operations needed to make the subarray arr1[0:i] strictly increasing.
  5. Loop through each element in arr1 (as i).
  6. If a is smaller than the current element in arr1, update new_dp[i] with the minimum operations p.
  7. If we are not at the first element and dp[i-1] is smaller than the current minimum operations, update p.
  8. Check if the current element is greater than the next one, if so return -1 (impossible to create an increasing array).
  9. After iterating all elements in arr1, swap dp with new_dp.
  10. Finally, return the last element in the dp array (minimum operations needed to make the entire arr1 strictly increasing).
🌐 Data from online sources 
#include <vector>
#include <limits>

int minOperations(std::vector<int>& arr1, std::vector<int>& arr2) {
    int n = arr1.size();
    std::vector<int> dp(n, std::numeric_limits<int>::max());
    for (int a : arr2) {
        std::vector<int> new_dp(n, std::numeric_limits<int>::max());
        int p = 0;
        for (int i = 0; i < n; ++i) {
            if (a < arr1[i]) new_dp[i] = p;
            if (i > 0 && dp[i - 1] < p) p = dp[i - 1];
            if (arr1[i] > arr1[i + 1]) return -1;
        }
        dp.swap(new_dp);
    }
    return dp.back();
}
  1. Initialize a dp array with the same length as arr1, fill it with infinity.
  2. Loop through each element in arr2 (as a).
  3. At each iteration, create a new dp array called new_dp.
  4. Use a variable p to track the minimum number of operations needed to make the subarray arr1[0:i] strictly increasing.
  5. Loop through each element in arr1 (as i).
  6. If a is smaller than the current element in arr1, update new_dp[i] with the minimum operations p.
  7. If we are not at the first element and dp[i-1] is smaller than the current minimum operations, update p.
  8. Check if the current element is greater than the next one, if so return -1 (impossible to create an increasing array).
  9. After iterating all elements in arr1, swap dp with new_dp.
  10. Finally, return the last element in the dp array (minimum operations needed to make the entire arr1 strictly increasing).