DSAPROB27 - Editorial

editorial
, , ,
1

Problem Link : Binary Linked List Representation

Problem Statement:

The task is to create a linked list that represents the binary representation of a given non-negative integer N and print the linked list in a readable format.

Approach:

The key idea is to create a linked list that represents the binary form of a non-negative integer N.

  • Node Structure: We define a Node struct with an integer data to hold a bit (0 or 1) and a pointer next to link to the next node.

  • Creating the Linked List:

    • If N is 0, we create a node with data 0 as the head.

    • For N > 0, we initialize the head as nullptr. We repeatedly extract the last bit of N using N % 2, create a new node with this bit, and insert it at the beginning of the list. We update the head to point to the new node and divide N by 2 to move to the next bit.

  • Printing the List: The printList function traverses the linked list and prints each node’s data, using " → " to show connections.

Time Complexity:

The time complexity is O(log N) because we process each bit of N, which takes logarithmic time relative to the value of N.

Space Complexity:

The space complexity is O(log N) for the linked list, as we create a node for each bit in the binary representation of N.