Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Binary list

Last Updated on May 23, 2022 by Ria Pathak

### CONCEPTS USED:

Basic Manipulation

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 :

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 *newnode = (struct Node*)malloc(sizeof(struct Node));
newnode->value = val ;
newnode->next = NULL ;
static Node *temp;
if ( head == NULL ) {
}
else
{
temp->next = newnode ;
temp =temp->next;
}
}

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

{
/* If list is empty or it contains only 1 bit */

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;
}

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;
}
}

/* 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];
}

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 *newnode = new Node;
newnode->value = val ;
newnode->next = NULL ;
static Node *temp;
if ( head == NULL ) {
}
else
{
temp->next = newnode ;
temp =temp->next;
}
}

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

{

int ones = 0, zeros = 0;

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

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;
}
}
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];
}

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

cout<<endl;
}
return 0;
}
```
```import java.io.*;
import java.util.*;
public class Main{
public char value;
this.value = nodeData;
this.next = null;
}
}

this.tail = null;
}

public void insertNode(char nodeData) {

} else {
this.tail.next = node;
}

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

{
/* If list is empty or it contains only 1 bit */

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;
}

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;
}
}

/* 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)
{
String str = scanner.next();
int size= str.length();

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

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

Space Complexity: `O(1)`

[forminator_quiz id="2127"]

This article tried to discuss Basic Manipulation. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Manipulation you can check out MYCODE | Competitive Programming.