Binary list

CONCEPTS USED:

Basic Manipulation

DIFFICULTY LEVEL:

Easy

PROBLEM STATEMENT(SIMPLIFIED):

Given a linked list of N nodes, each node containing binary bit either 0 or 1 as a character. Your task is to arrange nodes in such a way that no two consecutive nodes contain the same bit.

NOTE : The list must start from 0 if there is more than one bit.

See original problem statement here

For Example:

Input : 100101

Output: 010101

Explaination : As count of 0's and 1's are equal i.e. 3, so they can be arranged accordingly.
Input : 11001

Output: -1

Explaination : As count of 1's is greater than count of 0's, given string cannot be arranged in the required fashion.

OBSERVATION :

Learn programming languages online so that We can arrange our string in the required fashion if any of the two conditions are met -

  • count of 0's is equal to count of 1's

  • count of 0's is equal to count of 1's + 1

SOLVING APPROACH:

  1. Calculate the count of 0's and 1's in zeros and ones.

  2. Check if the string is empty or contains only 1 char, in this case our string is already arranged so return.

  3. Check if zeros = ones or zeros = ones + 1, if true one-by-one keep assigning the values of 0 and 1 to the string linearly. Else return.

SOLUTIONS:


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
    char value;
    struct Node* next;
}Node;

Node* CreateNode(Node *head, char val)
{
    Node *newnode = (struct Node*)malloc(sizeof(struct Node));
    newnode->value = val ;
    newnode->next = NULL ;
    static Node *temp;
    if ( head == NULL ) {
        head = newnode ;
        temp=head;
    }
    else
    {
        temp->next = newnode ;
        temp =temp->next;
    }
    return head ;
}


void printList(Node *head) {
    Node *temp = head ;
    if (temp) {
        while ( temp!= NULL ) {
            printf ( "%c", temp->value ) ;
            temp = temp->next ;
        }
    }
}

Node*  BinaryList(Node *head)
{
  /* If list is empty or it contains only 1 bit */
    if(head == NULL || head -> next == NULL)
      return head;

    Node *temp = head;
    int ones = 0, zeros = 0;

    /* Calculate count of 0's and 1's in the list */
    while(temp){
      if(temp -> value == '1')
        ones++ ;
      else
        zeros++ ;
      temp = temp -> next;
    }

    temp = head;
    int flag = 1;

    /* if count of 0's and 1's is valid arrange them accordingly */
    if((zeros == ones) || (zeros == (ones + 1))){
      while(temp){
        if(flag){
          temp -> value = '0';
          flag = 0;
        }
        else{
          temp -> value = '1';
          flag = 1;
        }
        temp = temp -> next;
      }
      return head;
    }

    /* if count of 0's and 1's is not valid return NULL */
    else
      return NULL;
}

int main() {

    int t;
    scanf("%d", &t);
    while(t--){

        Node *head = NULL, *temp ;
        char str[100005];
        scanf("%s", str);
        int size=strlen(str);
        for ( int i = 0 ; i < size ; i ++ ) {
            char ch=str[i];
            head = CreateNode(head, ch) ;
        }

        temp = BinaryList(head) ;
        if ( temp != NULL )
            printList(temp);
        else
            printf("-1");

        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
    char value;
    struct Node* next;
}Node;

Node* CreateNode(Node *head, char val)
{
    Node *newnode = new Node;
    newnode->value = val ;
    newnode->next = NULL ;
    static Node *temp;
    if ( head == NULL ) {
        head = newnode ;
        temp=head;
    }
    else
    {
        temp->next = newnode ;
        temp =temp->next;
    }
    return head ;
}


void printList(Node *head) {
    Node *temp = head ;
    if (temp) {
        while ( temp!= NULL ) {
            printf ( "%c", temp->value ) ;
            temp = temp->next ;
        }
    }
}


Node*  BinaryList(Node *head)
{
    // write your code here
    if(head == NULL || head -> next == NULL)
      return head;

    Node *temp = head;
    int ones = 0, zeros = 0;

    while(temp){
      if(temp -> value == '1')
        ones++ ;
      else
        zeros++ ;
      temp = temp -> next;
    }

    temp = head;
    int flag = 1;
    if((zeros == ones) || (zeros == (ones + 1))){
      while(temp){
        if(flag){
          temp -> value = '0';
          flag = 0;
        }
        else{
          temp -> value = '1';
          flag = 1;
        }
        temp = temp -> next;
      }
      return head;
    }
    else
      return NULL;
}

int main() {

    int t;
    cin>>t;
    while(t--){

        Node *head = NULL, *temp ;
        string str;
        cin>>str;
        int size=str.length();
        for ( int i = 0 ; i < size ; i ++ ) {
            char ch=str[i];
            head = CreateNode(head, ch) ;
        }

        temp = BinaryList(head) ;
        if ( temp != NULL )
            printList(temp);
        else
            cout<<-1;

        cout<<endl;
    }
    return 0;
}

import java.io.*;
import java.util.*;
public class Main{
    static class SinglyLinkedListNode {
        public char value;
        public SinglyLinkedListNode next;
        public SinglyLinkedListNode(char nodeData) {
            this.value = nodeData;
            this.next = null;
        }
    }
    static class SinglyLinkedList {
        public SinglyLinkedListNode head;
        public SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            this.head = null;
            this.tail = null;
        }

        public void insertNode(char nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }

            this.tail = node;
        }
    }
    static void printLinkedList(SinglyLinkedListNode head)
    {
        SinglyLinkedListNode temp=head;
        while(temp!=null)
        {
            System.out.print(temp.value);
            temp=temp.next;
        }
        System.out.println();
    }

    static SinglyLinkedListNode BinaryList(SinglyLinkedListNode head)
    {
      /* If list is empty or it contains only 1 bit */
    if(head == null || head.next == null)
      return head;

    SinglyLinkedListNode temp = head;
    int ones = 0, zeros = 0;

    /* Calculate count of 0's and 1's in the list */
    while(temp != null){
      if(temp.value == '1')
        ones++ ;
      else
        zeros++ ;
      temp = temp.next;
    }

    temp = head;
    int flag = 1;

    /* if count of 0's and 1's is valid arrange them accordingly */
    if((zeros == ones) || (zeros == (ones + 1))){
      while(temp != null){
        if(flag == 1){
          temp.value = '0';
          flag = 0;
        }
        else{
          temp.value = '1';
          flag = 1;
        }
        temp = temp.next;
      }
      return head;
    }

    /* if count of 0's and 1's is not valid return NULL */
    else
      return null;
    }


    private static final Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) throws IOException {

        int testCases = scanner.nextInt();
        while (testCases-- > 0)
        {
            SinglyLinkedList llist = new SinglyLinkedList();
            String str = scanner.next();
            int size= str.length();

            for (int i = 0; i < size; i++) {
                char ch = str.charAt(i);

                llist.insertNode(ch);
            }
            SinglyLinkedListNode temp = BinaryList(llist.head);
            if(temp!=null)
                printLinkedList(temp);
            else
                System.out.println("-1");
        }
    }
}

Space Complexity: O(1)

Previous post Number of islands
Next post Contest Winner

Leave a Reply

Your email address will not be published. Required fields are marked *