Sarthak Mall
BAN USERyou have to do 3 task for making it simple ,break in three process
1)print all the left node.
2)print all the leaf.
3)print all the right node.
struct node
{
int data;
node *l,*r;
};
#include<iostream>
using namespace std;
node *create_node(int data);
void perimeter(node *root);
void print_r_child(node *root);
void print_l_child(node *root);
void print_leaves(node *root);
int main()
{
node * root = NULL;
root = create_node(1);
root->l = create_node(2);root->r = create_node(3);
root->l->l = create_node(4);root->l->r = create_node(5);
root->r->l = create_node(6);root->r->r = create_node(7);
root->l->l->l = create_node(8);root->l->l->r = create_node(9);
root->l->r->l = create_node(10);root->l->r->r = create_node(11);
perimeter(root);
return 0;
}
void perimeter(node *root)
{
if(root) cout<<root->data<<" ";
print_l_child(root->l);
print_leaves(root);
print_r_child(root->r);
}
void print_l_child(node *root)
{
if(root->l!=NULL)
{
cout<<root->data<<" ";;
print_l_child(root->l);
}
}
void print_r_child(node *root)
{
if(root->r!=NULL)
{
print_r_child(root->r);
cout<<root->data<<" ";
}
}
node *create_node(int data)
{
node *newnode = new node;
newnode->data = data;
newnode->l = newnode->r = NULL;
return newnode;
}
void print_leaves(node *root)
{
if(!(root->l && root->r))
{
cout<<root->data<<" ";
return;
}
if(root->l) print_leaves(root->l);
if(root->r) print_leaves(root->r);
}
A simple modified binary search would work...
#include<iostream>
using namespace std;
int Min(int arr[],int size);
int main()
{
int arr[] = {4,5,6,7,8,9,1,2,3};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<Min(arr,size);
return 0;
}
int Min(int arr[],int size)
{
if(size==1) return arr[0];
int l = 0,h = size-1,m;
while(l<h)
{
if(l+1 == h) return min (arr[l],arr[h]);
m = l + (h-l)/2;
if(arr[l]>arr[m]) h = m;
else if(arr[l]<arr[m]) l = m;
else return arr[m];
}
}
A simple O(n) approach
#include<iostream>
using namespace std;
void sort01(int arr[],int size);
int main()
{
int arr[] = {0,0,1,0,1,1,1,0,0,0};
int size = sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<size;i++) cout<<arr[i]<< " ";
sort01(arr,size);
cout<<endl;
for(int i=0;i<size;i++) cout<<arr[i]<< " ";
cout<<endl;
return 0;
}
void sort01(int arr[],int size)
{
int h = size-1,l = 0;
int temp;
while(l<h)
{
while(arr[l] == 0 && l<h) l++;
while(arr[h] == 1 && l<h ) h--;
if(l<h){
temp = arr[l];
arr[l] = arr[h];
arr[h] = temp;
l++;
h--;
}
}
}
I think it is very simple.Just find out the intersection point in this case. in the process of finding intersection point we should just keep track of previous node whose next node is the intersection point.
here is the code..
struct node
{
int a;
node *next;
};
#include<iostream>
using namespace std;
void insert(node **head,int data);
void printList(node *head);
node * get_last_node_loop(node *head);
int main()
{
node *head = NULL;
for(int i = 10;i>0;i--) insert(&head,i);
//Print list having no loop
printList(head);
//Create a cycle
node *temp = head;
for(int i = 0;i<9;i++) temp = temp->next;
temp->next = head->next->next->next->next;
node *last = get_last_node_loop(head);
cout<<"Last = "<<last->a<<"\n";
return 0;
}
void insert(node **head,int data)
{
node *newnode = new node;
newnode->a = data;
newnode->next = *head;
*head = newnode;
}
void printList(node *head)
{
while(head!=NULL)
{
cout<<head->a<<"-->";
head = head->next;
}
}
node * get_last_node_loop(node *head)
{
//little variation in the loop finding code
node * slow = head,*fast = head;
slow = head->next;
fast = head->next->next;
while(slow!=fast)
{
slow = slow->next;
fast = fast->next->next;
}
slow = head;
node *prev ;
while(slow!=fast)
{
prev = fast;
slow = slow->next;
fast = fast->next;
}
return prev;
}
If all the elements are -ve than print the one having smallest magnitude
else
take into account only +ve numbers.
- Sarthak Mall June 02, 2013