Last Updated on May 23, 2022 by Ria Pathak
CONCEPTS USED:
Basic Manipulation
DIFFICULTY LEVEL:
Easy
PROBLEM STATEMENT(SIMPLIFIED):
Given a linked list of
Nnodes, each node containing binary bit either0or1as 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
0if 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 of1‘scount of
0‘s is equal to count of1‘s+ 1
SOLVING APPROACH:
- Calculate the count of
0‘s and1‘s inzerosandones.- Check if the string is empty or contains only
1char, in this case our string is already arranged so return.- Check if
zeros=onesorzeros=ones + 1, if true one-by-one keep assigning the values of0and1to 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)
[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.