Jobs

Interviews

Discussions

Convert Binary Number in a Linked List to Integer

Easy

Amazon

5 views

Topics:

Linked ListsBit Manipulation

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.

Convert Binary Number in a Linked List to Integer

Easy

Amazon

5 views

Topics:

Linked ListsBit Manipulation

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain null values?
What is the maximum length of the linked list? Is there a limit to the number of nodes?
Are the values of the nodes guaranteed to be either 0 or 1, or could they be other integers?
Should I return 0 if the linked list is empty?
Can the resulting integer exceed the maximum value that can be stored in a standard integer data type? If so, what should the return type be?

Brute Force Solution

Approach

We're given a linked list representing a binary number and we want to find its decimal equivalent. The brute force approach involves figuring out the complete binary number first, then converting that entire number into its decimal form at once.

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Walk through the entire list, remembering each 0 or 1 you see, one by one, in the order you see them.
Put all those 0s and 1s together to form a complete binary number.
Now, take that complete binary number and convert it into its equivalent decimal number.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getDecimalValue(head):
    binary_string = ""
    current_node = head

    # Traverse the linked list to construct the binary string
    while current_node:
        binary_string += str(current_node.val)
        current_node = current_node.next

    # Convert the binary string to an integer
    decimal_value = 0
    power = 0

    # Iterate through the binary string in reverse.
    for bit in reversed(binary_string):
        if bit == '1':
            decimal_value += 2 ** power
        power += 1

    return decimal_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list of size n once to construct the binary number string. Then, converting the binary string to an integer takes time proportional to the length of the string, which is also n. Therefore, the overall time complexity is dominated by a single linear pass through the list plus the conversion, resulting in O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The provided solution constructs a complete binary number string by traversing the linked list. This string requires memory proportional to the number of nodes (N) in the linked list to store all the 0s and 1s. Therefore, the algorithm uses auxiliary space to store a string of length N, where N represents the number of nodes in the linked list. Consequently, the space complexity is O(N).

Optimal Solution

Approach

We need to turn a linked list representing a binary number into its integer equivalent. The most efficient way to do this is to construct the integer representation bit by bit as we traverse the list, leveraging the binary number system's properties.

Here's how the algorithm would work step-by-step:

Start with an integer initialized to zero. This will hold our result.
Move through the linked list one node at a time, beginning with the head (most significant bit).
For each node, shift the current integer value to the left by one position (multiply by two). This makes space for the new bit.
Add the value of the current node (either 0 or 1) to the integer.
Repeat steps three and four until you reach the end of the linked list.
The final integer value is the decimal representation of the binary number.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_decimal_value(head: ListNode) -> int:
    decimal_value = 0

    current_node = head

    # Iterate through the linked list
    while current_node:
        # Shift existing bits to the left, making space for the new bit.
        decimal_value = decimal_value * 2

        # Add the current node's value (0 or 1) to the result.
        decimal_value = decimal_value + current_node.val

        current_node = current_node.next

    return decimal_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the linked list once, where n is the number of nodes in the list, representing the number of bits in the binary number. For each node, a fixed number of operations (left shift and addition) are performed. Therefore, the time complexity is directly proportional to the number of nodes, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm uses a single integer variable to store the result as it iterates through the linked list. No additional data structures that scale with the input size N (the number of nodes in the linked list) are created. Therefore, the space used is constant and independent of the input size.

Edge Cases

Case	How to Handle
Empty list	Return 0 immediately as an empty list represents the integer 0.
Single node list with value 0	Return 0 as the single node list [0] represents the integer 0.
Single node list with value 1	Return 1 as the single node list [1] represents the integer 1.
List with all zeros	This represents the integer 0, and the iterative or recursive solution should handle it correctly by resulting in 0.
Very long list approaching integer overflow	Use a long data type or consider using BigInteger in languages like Java or Python to prevent integer overflow, or check for overflow during calculation.
List contains values other than 0 or 1	Throw an IllegalArgumentException or return an error code, as the input is invalid for a binary number representation.
List representing the maximum possible integer value for the system architecture	The conversion process should correctly calculate and return the maximum integer value without overflow if `long` data type is used.
List starting with multiple leading zeros	The conversion algorithm should correctly interpret these leading zeros without affecting the resulting integer value (e.g., [0,0,1] should return 1).

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty or contain null values?
What is the maximum length of the linked list? Is there a limit to the number of nodes?
Are the values of the nodes guaranteed to be either 0 or 1, or could they be other integers?
Should I return 0 if the linked list is empty?
Can the resulting integer exceed the maximum value that can be stored in a standard integer data type? If so, what should the return type be?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the beginning of the linked list.
Walk through the entire list, remembering each 0 or 1 you see, one by one, in the order you see them.
Put all those 0s and 1s together to form a complete binary number.
Now, take that complete binary number and convert it into its equivalent decimal number.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getDecimalValue(head):
    binary_string = ""
    current_node = head

    # Traverse the linked list to construct the binary string
    while current_node:
        binary_string += str(current_node.val)
        current_node = current_node.next

    # Convert the binary string to an integer
    decimal_value = 0
    power = 0

    # Iterate through the binary string in reverse.
    for bit in reversed(binary_string):
        if bit == '1':
            decimal_value += 2 ** power
        power += 1

    return decimal_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with an integer initialized to zero. This will hold our result.
Move through the linked list one node at a time, beginning with the head (most significant bit).
For each node, shift the current integer value to the left by one position (multiply by two). This makes space for the new bit.
Add the value of the current node (either 0 or 1) to the integer.
Repeat steps three and four until you reach the end of the linked list.
The final integer value is the decimal representation of the binary number.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def get_decimal_value(head: ListNode) -> int:
    decimal_value = 0

    current_node = head

    # Iterate through the linked list
    while current_node:
        # Shift existing bits to the left, making space for the new bit.
        decimal_value = decimal_value * 2

        # Add the current node's value (0 or 1) to the result.
        decimal_value = decimal_value + current_node.val

        current_node = current_node.next

    return decimal_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty list	Return 0 immediately as an empty list represents the integer 0.
Single node list with value 0	Return 0 as the single node list [0] represents the integer 0.
Single node list with value 1	Return 1 as the single node list [1] represents the integer 1.
List with all zeros	This represents the integer 0, and the iterative or recursive solution should handle it correctly by resulting in 0.
Very long list approaching integer overflow	Use a long data type or consider using BigInteger in languages like Java or Python to prevent integer overflow, or check for overflow during calculation.
List contains values other than 0 or 1	Throw an IllegalArgumentException or return an error code, as the input is invalid for a binary number representation.
List representing the maximum possible integer value for the system architecture	The conversion process should correctly calculate and return the maximum integer value without overflow if `long` data type is used.
List starting with multiple leading zeros	The conversion algorithm should correctly interpret these leading zeros without affecting the resulting integer value (e.g., [0,0,1] should return 1).