Equal Squares - Greatest Common Divisor

Problem Discussion:

You have been provided with a paper of dimensions NxM. You have to cut this paper according to the following rules:

1. Paper should be cut along a line parallel to one of the sides of the paper.
2. Paper is cut such that the resultant dimensions are always integer. 

 You need to calculate the minimum number of squares (all of equal size) that can be formed from the given piece of paper.

Input:
The very first line consist of an integer T, total number of testcases. After which T lines follow and each line consist of two space separated integers N and M, dimensions for paper.

Output:
You need to output the required answer, an integer value.

Constraints:

1<=T<=100000
1<=N,M<=10000

Example:
Input:
2
1 1
1 2

Output:
1
2

Algorithm:
To find the minimum number of squares, find the biggest square that can be formed such that all the resulting squares are of equal size.To find the biggest square, calculate the gcd of N and M. The maximum square formed is of the dimension gcd(N,M)xgcd(N,M).
Now to find the minimum number squares, divide the total area of the given piece of paper by the area of the maximum square formed.

Therefore,
Answer=( NxM )/( gcd(N,M) x gcd(N,M) )

Solution:

/*
Date:18th September 2014
Contest:CodeSprint 2k14
Program Code:
Program Description:Cutting paper

submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
int n = 0;
register char c = getchar_unlocked();//register is used due to its repeated use
while (!('0' <= c && c <= '9'))
  {
  c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
{
  n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
  c = getchar_unlocked();
}
 return n;
}
int GCD(int a,int b )
{
  if ( a < b )
  return GCD( b, a );
  if ( b == 0 ) return a;
return GCD( b, a % b );
}

int main()
{
int test;
scanf("%d",&test);
while(test--)
{
int N,M,gcd;
N=read();
M=read();
gcd=GCD(N,M);
N=N/gcd;
M=M/gcd;
cout<<N*M<<endl;
}
// getchar();
return 0;

}

Rachelle and Interest - Modulus Properties

Problem Discussion:

Rachelle Green has taken loan of $1 from the Byteland Bank.After each passing day, Rachelle is required to pay A times the amount on the previous day.Rachelle wants to know the amount which she has to pay after Xth day.

Rachelle Green being poor in calculations, has come to you for the help.Since, the answer can be very large, tell her answer modulo 1000000007.

Input:

The first line contains an integer T, the number of testcases.It's followed by T lines.Each testcase will contain two integers, A and X, separated with a space.

Ouptut:

Output T lines, each corresponding to the answer of the testcase.

Constraints:

1<=T<=10
1<=A,B<=10^100000

Example:

Input:

5
3 2
4 5
7 4
34534985349875439875439875349875 93475349759384754395743975349573495
34543987529435983745230948023948 3498573497543987543985743989120393097595572309482304

Output:

9
1024
2401
735851262
985546465

Algorithm:

Here we just have to calculate A^X but the challenge is that we cannot accommodate the values of A and X in integer data type.To solve this, we can make use of following properties:

1.( a ^ x ) % m can be calculated as ( a % m ) ^ ( x % (m-1) ).

2.For large numbers' modulus calculation, we can make use of Horner's Method. 

3.And, can further calculate power in O(log n) time complexity.

Solution:

/*
Program Description:Rachelle and Interest - Modulus Properties

submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<vector>
#define MAX 100001
#define MOD 1000000007
//#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
 int n = 0;
 register char c = getchar_unlocked();//register is used due to its repeated use
 while (!('0' <= c && c <= '9'))
  {
    c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
 {
   n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
   c = getchar_unlocked();
 }
 return n;
}
LL Horner(char A[MAX],LL M)
{
 LL i=0,a=0;
 while(A[i])
    {
        a=(a*10+(A[i]-'0'))%M;
     i++;
    }
    return a;
}
LL power(LL a,LL x)
{
 LL res = 1;
 while(x > 0)
 {
  if( x % 2 != 0) 
  {
   res = (res * a) % MOD;
  }
  a = (a * a) % MOD;
  x /= 2;
 }
 return res;
}
int main()
{
 int test;
 scanf("%d",&test);
 while(test--)
 {
  char A[MAX]={},X[MAX]={};
  scanf(" %s",A);
  scanf(" %s",X);
  LL a,x;
  a=Horner(A,MOD);
  x=Horner(X,MOD-1);
  printf("%lld\n",power(a,x));
 }
// getchar();
 return 0;
}

Cities of Different Nations (Graph Theory):Breadth First Search Implementation and Combinatorics

Problem Discussion:

There are N cities numbered from 0 to N-1.Consider a country to be a set of many cities.For more clarity, all the cities in a country are somehow connected to each other.If A is a part of a country C, and B is connected to A, then B too lies in country C.  

The Prime Minister of Byteland wants to go to any two cities.The Prime Minister loves travelling and therefore, he wants to visit cities of different nations.Prime Minister, therefore, asked his Personal Assistant to calculate the number of ways of choosing two cities such that they are from different countries.

The Personal Assistant is not good in mathematics and therefore, has come to you for the answer.

Input:

The very first line contains an integer N, number of cities.The next line contains an integer P, total number of given connections.The ith line of the next P lines contains two integers Xi and Yi, meaning Xi and Yi cities are part of the same country.

Output:

Print the required answer, an integer, in a single line.

Constraints:

1<=N<=100000
0<=P<=min(N*(N+1)/2,100000)

Example:

Input:

4

2

0 1

2 3

Output:

4

Explaination:

Sets {0,1} and {2,3} form two countries.Two cities can be chosen in following ways:

city 0 and city 2

city 0 and city 3

city 1 and city 2

city 1 and city 3

Therefore, total number of ways of choosing two cities are 4.

Algorithm:

To find the required answer, we must know the number of cities in each nation.For calculating the number of cities in each nation, we can use Breadth First Search Algorithm.

Now, the if there are M nations and the total number of cities in ith nation be iCity then the required answer, Ans can be calculated as:

Solution:

/*

Problem Description:Cities of Different Nations

Submitted By

Arjun Mishra

*/

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

typedef long long LL;

vector<LL> AdjList[100001];

queue<LL> Q;

LL count[100001],c=0,visited[100001]={},sum=0;

int main()

{

    LL i,N,L;

    cin>>N>>L;

    while(L--)

    {

        LL a,b;

        cin>>a>>b;

        AdjList[a].push_back(b);

        AdjList[b].push_back(a);

    } 

    //finding connected streaks

    for(i=0;i<N;i++)

    {

        LL ct=1;

        if(!visited[i])

        {

            visited[i]=1;

Q.push(i);

            while(!Q.empty())

            {

                LL temp,len;

                temp=Q.front();

                Q.pop();

                len=AdjList[temp].size();

                for(LL j=0;j<len;j++)

                {

                    if(!visited[AdjList[temp][j]])

                    {

                        ct++;

                        visited[AdjList[temp][j]]=1;

                    }   

                    Q.push(AdjList[temp][j]);

                }    

                AdjList[temp].clear();

        }

        count[c++]=ct;  

            sum+=ct;

        }    

    }

    LL ans=0;

    for(i=0;i<c;i++)

    {

        ans+=count[i]*(sum-count[i]);

    }    

    cout<<(ans/2)<<endl;

    return 0;

}

Even Forests (Graph Theory): Depth First Search Implementation

Problem Statement:

As we all know that Tree is basically a subset of Graph; a simple connected graph with no cycles.A tree with N nodes (numbered as 1,2,3,..,N) has N-1 edges.Forest is created when there exists two or more independent trees in a graph.Forest can be created by removing edges from a tree.

In this problem you will be given a tree with N nodes.You have to remove as many edges from the tree as possible to obtain a forest with condition that : Each connected component of the forest should contain even number of vertices.

Your task is to calculate the number of independent trees in that forest.

Consider that the tree is rooted at 1.

Input:

The first line of the input contains an integer N, where N is the number of nodes in a tree.Following N-1 lines contains two integers X and Y, where X is a child of Y.

Output:

Print the answer, a single integer.

Constraints:

1<=N<=100000
1<=X,Y<=N
                                                                                     
Example:

Input:

10
2 1
3 1
4 3                                          
5 2                                                                                      ORIGINAL TREE
6 1
7 2
8 6
9 8
10 8




Output:                                  
3                                                                              




                                                                                          DECOMPOSED TREE
Algorithm:

The problem can be easily solved using Depth First Search.For every node maintain the count information regarding total number of nodes for which the current node is their ancestor.

Solution:

/*
Problem Description:Even Forests

Submitted By
Arjun Mishra
*/

#include<iostream>
#include<vector>
#define MAX 100001
using namespace std;
vector<int> AdjList[MAX];
int nChild[MAX]={};
int dfs(int source)
{
int len=AdjList[source].size();
if(len==0)
{
nChild[source]=1;
return 1;
}
for(int i=0;i<len;i++)
{
nChild[source]+=(dfs(AdjList[source][i]));
}
nChild[source]+=1;
return nChild[source];
}
int main()
{
    int N,E;
    cin>>N;
    E=N-1;//number of edges in a tree
    while(E--)
    {
        int x,y;
        cin>>x>>y;//x is a child of y
        AdjList[y].push_back(x);
    }  
    //applying dfs
    int source=1,count=0;
    dfs(source);
    //counting ancestors with even number of nodes under them
    for(int i=1;i<=N;i++)
    if(nChild[i]%2==0)
    count++;
    //output, required answer
    cout<<count<<endl;
    return 0;

}    

Coding a Trie

Definition :

Trie is also called Digital Tree (sometimes Radix Tree or Prefix Tree).It is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

Solution:

/*
Trie Data Structure

Submitetd By
Arjun Mishra
*/

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define MAX_SIZE 26

//data structure for Trie<only for small letters>
struct Trie
{
int count;
int leaf;
struct Trie* next[MAX_SIZE];
Trie()//constructor
{
count=0;//initially not visited
leaf=0;//initially 0, means not a leaf
for(int i=0;i<MAX_SIZE;i++)
next[i]=NULL;//initially NULL
}
}*root,*ptr;

//function to insert into a trie
void insert(char str[6],int index,int len,struct Trie *R)
{
if(index==len)
{
return;
}
if(R->next[str[index]-'a']==NULL)
{
ptr=new Trie();
R->next[str[index]-'a']=ptr;
}
R->next[str[index]-'a']->count+=1;
if(index==(len-1))
R->next[str[index]-'a']->leaf=1;
insert(str,index+1,len,R->next[str[index]-'a']);
}

//function to traverse a trie
void getWords(struct Trie *R,char o[51],int index)
{

if(R==NULL)
return;
for(int i=0;i<MAX_SIZE;i++)
{
if(R->next[i]!=NULL)
{
//cout<<index<<endl;
o[index]=char(i+97);
if(R->next[i]->leaf==1)
{
for(int j=0;j<=index;j++)
cout<<o[j];
cout<<endl;
}
getWords(R->next[i],o,index+1);
}
}
}

//function to perform sleep operation
void sleep(int time_in_sec)
{
int start=clock();
while(clock()<=(start+time_in_sec*1000))
{
//empty loop
}
}

//main function, driver utility
int main()
{
ptr=new Trie();
root=ptr;
while(1)
{
int ch;
char str[51]={};
char o[51]={};
cout<<"Menu :\n\n";
cout<<"Enter 0 to exit\n";
cout<<"Enter 1 to insert into the dictionary\n";
cout<<"Enter 2 to traverse dictionary\n";
cout<<"\nEnter your choice :";
cin>>ch;
switch(ch)
{
case 0:
system("cls");
cout<<"Application By :\n\nArjun Mishra\nFinal Year Student\nMNNIT Allahabad";
return 0;
case 1:
system("cls");
cout<<"Insert word :";
scanf(" %s",str);
insert(str,0,strlen(str),root);
system("cls");
break;
case 2:
system("cls");
cout<<"All inserted words are\n\n";
getWords(root,o,0);
cout<<"\n\nPlease Wait...";
sleep(5);
system("cls");
break;
default:
system("cls");
cout<<"Wrong Choice\n";
sleep(2);
system("cls");
}
}
return 0;

}

Reverse Edges : Dijkstra's Algorithm Implementation

You have been given a directed graph consisting of N nodes and M edges.Vertices are numbered from 1 to N.The problem is to find the minimum number of edges that are needed to be reversed to reach the destination node from vertex 1.

Input:

The first line of the input contains two space separated integers N and M, denoting number of vertices and the number of edges respectively.The next ith line of the next M lines consists of two space separated integers Xi and Yi, denoting an edge directed from Xi to Yi.The last line of the input consists of an integer D, denoting the destination vertex.

Constraints:

1<=N,M<=100000

1<=Xi,Yi<=N

There can be multiple edges connecting the same pair of vertices.

There can be self loops too.

Output:

In a single line, print the minimum number of edges that we need to revert.If there is no way of reaching vertex D from vertex 1, print -1.

Example:

Input:
7 7
1 2 
3 2
3 4
7 4
6 2
5 6
7 5

7

Output:
2

Algorithm:




We will apply Dijkstra's Algorithm(for single source shortest path) to solve the given problem.Let the weight of the provided edges be 0 and for each given edge ,add a reverse edge of it having weight 1 unit.Now, apply Dijkstra's Algorithm for finding the minimum weighted path(path with minimum edges reversed) from vertex 1, or vertex 1 as a source.





Solution:


/*
Reverse Edges


submitted by
Arjun Mishra
*/
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define pp pair<int,int>
#define MAX 100001
#define INF 1000000000
//#define getchar_unlocked() getchar()
typedef long long LL;
using namespace std;
inline int read() //faster input for integer
{
 int n = 0;
 register char c = getchar_unlocked();//register is used due to its repeated use
 while (!('0' <= c && c <= '9'))
  {
    c = getchar_unlocked();
  }
  while ('0' <= c && c <= '9')
 {
   n = (n<<3) + (n<<1) +  c - '0';//equivalent to n = n*10 + c - 48;
   c = getchar_unlocked();
 }
 return n;
}
struct Prior
{
 int operator() ( const pair<int, int>& p1, const pair<int, int>& p2 )
    {
        return p1.second > p2.second;
    }
};
vector<pp> AdjList[MAX];
int dist[MAX],visited[MAX]={};
priority_queue<pp, vector<pp > , Prior > Queue;
//precomputation
void precompute()
{
 for(int i=0;i<MAX;i++)
 dist[i]=INF;//initially distance between vertex 1 and other vertices is infinity
}
int main()
{
 precompute();
 int N,M,D;
 N=read();
 M=read();
 while(M--)
 {
  int u,v;
  u=read();
  v=read();
        AdjList[u].push_back(pp(v,0));//given edge with weight 0
        AdjList[v].push_back(pp(u,1));//reverse edge with weight 1
 }
 D=read();
 //applying dijkstra
 int source=1;
    dist[source] = 0;
    Queue.push(pp(source,dist[source]));
    while(!Queue.empty())
    {
        int u,v,w;
 u = Queue.top().first;
        Queue.pop();
        int size = AdjList[u].size();
        for(int i = 0 ; i < size ; i++)
        {
            v = AdjList[u][i].first;
            w = AdjList[u][i].second;
            if(dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                Queue.push(pp(v,dist[v]));
            }
        }
    AdjList[u].clear();
    }
    if(dist[D]==INF)//no path from 1 to D
    printf("-1\n");
    else
    printf("%d\n",dist[D]);
    return 0;
}

Detecting and printing a cycle from a Graph

The question is to detect and print any cycle, if exists, in a given graph else print -1.The question was asked by Amazon during on-campus recruitment coding round.

Algorithm:

The question can be solved using Depth First Search.Existence of cycle can be easily detected if we again reach an element which was already visited.

Input

The very first line denotes number of nodes,N, in a given graph.Following lines will contain two inputs, s and d, which signifies that there is a directed edge from node s to node d.The inputs will terminate at -1.

Output

We have to output the edges forming any one of the cycle in the format s->d.Every edge should occupy new line.

Constraints
1<=N<=10000

example:

input                           output
4                                 1->2
1 2                              2->4
2 4                              4->3
1 4                              3->1
4 3
3 1
-1

See the graph image.Red edges are the provided directed edges.While yellow edges are those which form a cycle.

Implementation:

/*
Problem Description: Detect and print a cycle from a graph

Submitted By:
Arjun Mishra
*/

#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define MAX 100001
vector<int> AdjList[MAX];
int N;//no of nodes
int mark;//mark is the node which is repeated
//function to find whether cycle exists or not, it is nothing but dfs implementation
int findCycle(int visited[MAX],int level,int output[MAX],int *index)
{
if(level>N)
return 0;
int l=AdjList[level].size(),i;
for(i=0;i<l;i++)
{
if(!visited[AdjList[level][i]])//if the node is visited for the first time
{
visited[AdjList[level][i]]=1;
output[(*index)++]=AdjList[level][i];
return findCycle(visited,AdjList[level][i],output,index);
}
else//if the node already is visited
{
mark=AdjList[level][i];
return 1;//condition is true as cycle detected
}
}
return 0;//no cycle found
}
//driver utility
int main()
{
int i;
cin>>N;
while(1)
{
int a,b;
cin>>a;
if(a==-1)
break;
cin>>b;
AdjList[a].push_back(b);//maintaining adjacency list
}

for(i=1;i<=N;i++)
{
int output[MAX],visited[MAX]={},*index,flag=0,s=0;
index=&s;
visited[i]=1;
output[*index]=i;
*index=(*index)+1;
flag=findCycle(visited,i,output,index);//calling findCycle utility
if(flag)//printing cycle if flag==1, meaning cycle detected
{
int f=0,j;
//printing the cycle
for(j=0;j<(*index)-1;j++)
{
if(output[j]==mark)
{
f=1;
}
if(f)
printf("%d->%d\n",output[j],output[j+1]);
}
printf("%d->%d\n",output[j],mark);

printf("\n");
//exit
return 0;
}
}
printf("-1\n");//no cycle detected
//end of program
return 0;
}

Intersection of two sorted Lists

Here's the implementation:

/*
Problem Description:
Intersection of two sorted list

submitted by
Arjun Mishra
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
//structure of node having elements of list1
struct node1
{
       int data;
       struct node1 *next;       
}*head1,*tail1,*temp1;
//structure of node having elements of list2
struct node2
{
       int data;
       struct node2 *next;       
}*head2,*tail2,*temp2;
//structure of node having elements of intersect
struct node
{
       int data;
       struct node *next;       
}*head,*tail,*temp;
//utility to insert the elemnets in list1
void push1(int val)
{
     temp1=(struct node1*)malloc(sizeof(struct node1));
     if(!temp1)
     {
               printf("Error:unable to allocate memory\n");
               return;
     }
     temp1->data=val;
     temp1->next=NULL;
     if(head1==NULL)
     {
               head1=temp1;
               tail1=temp1;      
     }           
     else
     {
               tail1->next=temp1;
               tail1=temp1;  
     }     
}
//utility to inesert the elements in list2
void push2(int val)
{
     temp2=(struct node2*)malloc(sizeof(struct node2));
     if(!temp2)
     {
               printf("Error:unable to allocate memory\n");
               return;
     }
     temp2->data=val;
     temp2->next=NULL;
     if(head2==NULL)
     {
               head2=temp2;
               tail2=temp2;      
     }           
     else
     {
               tail2->next=temp2;
               tail2=temp2;  
     }     
}
//utility push the intersected elements
void push(int val)
{
     temp=(struct node*)malloc(sizeof(struct node));
     if(!temp)
     {
               printf("Error:unable to allocate memory\n");
               return;
     }
     temp->data=val;
     temp->next=NULL;
     if(head==NULL)
     {
               head=temp;
               tail=temp;      
     }           
     else
     {
               tail->next=temp;
               tail=temp;  
     }     
}
//utility to traverse the intersected linked list
void traverse1()
{
     if(head1==NULL)
     {
               cout<<"No intersection!\n";
               return;    
     }     
     temp1=head1;
     while(temp1!=NULL)
     {
               cout<<temp1->data<<"->";
               temp1=temp1->next;       
     }
     cout<<"NULL"<<endl;
}
//utility to traverse the intersected linked list
void traverse2()
{
     if(head2==NULL)
     {
               cout<<"No intersection!\n";
               return;    
     }     
     temp2=head2;
     while(temp2!=NULL)
     {
               cout<<temp2->data<<"->";
               temp2=temp2->next;       
     }
     cout<<"NULL"<<endl;
}
//utility to traverse the intersected linked list
void traverse()
{
     if(head==NULL)
     {
               cout<<"No intersection!\n";
               return;    
     }     
     temp=head;
     while(temp!=NULL)
     {
               cout<<temp->data<<"->";
               temp=temp->next;       
     }
     cout<<"NULL"<<endl;
}
//utility to find the intersection
void findIntersection(struct node1 *head1,struct node2* head2)
{
     if(head1==NULL||head2==NULL)
     {
               head=NULL;
               return;
     }
     temp1=head1;
     temp2=head2;
     while(temp1!=NULL&&temp2!=NULL)
     {
               if(temp1->data==temp2->data)
               {
               push(temp1->data);
               temp1=temp1->next;
               temp2=temp2->next;
               }
               else if(temp1->data<temp2->data)
               temp1=temp1->next;
               else
               temp2=temp2->next;         
     }
     //calling traverse function to traverse the list
     cout<<"resultantList   :\t";
     traverse();                    
}

int main()
{
    //inserting elements in list1
    push1(1);
    push1(2);
    push1(3);
    push1(4);
    push1(6);
    cout<<"List 1  :\t";
    traverse1();
    cout<<endl<<endl;
    //inserting elements in list2
    push2(2);
    push2(4);
    push2(6);
    push2(8);
    cout<<"List 2  :\t";
    traverse2();
    cout<<endl<<endl;
    //calling the function findIntersect to find the intersection
    findIntersection(head1,head2);
    return 0;    
}

Detect Loop in a Linked List

Floyd’s Cycle-Finding Algorithm:

This is the fastest method. Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Solution:

/*
problem decription:detect loop in a linked list
method's name:floyd's cycle detection

solved by
Arjun Mishra
*/
#include<iostream>
#include<stdlib.h>
using namespace std;
//node structure
struct node
{
       int data;
       struct node *next;
}*head,*tail,*temp;

void push()//function to push a node in the linked list
{
     temp=(struct node*)malloc(sizeof(struct node));
     if(!(temp))
     {
      cout<<"memory not available!\n";
      return;
     }
     cout<<"Enter the data\n";
     cin>>temp->data;
     temp->next=NULL;
     if(head==NULL)//very first node marked as head
     {
      head=temp;
      tail=temp;
     }
     else//for subsequent nodes,tail pointer is moved
     {
      tail->next=temp;
      tail=temp;
     }
}
bool detect_loop()//function to detect a loop
{
     //floyd's cycle algo implementation
     bool flag=false;
     node *slowptr,*fastptr;
     slowptr=head;
     fastptr=head;
     while(slowptr&&fastptr&&fastptr->next)
     {
      slowptr=slowptr->next;
      fastptr=fastptr->next;
      fastptr=fastptr->next;
      if(slowptr==fastptr)
      {
       flag=true;
       break;
      }
     }
     return flag;
}
int main()
{
    char flag;
    while(1)
    {
     cout<<"Do you wanna push...\n";
     cin>>flag;
     switch(flag)
     {
      case 'y':
      case 'Y':
           push();
           break;
      case 'n':
      case 'N':
           break;
      default:
           cout<<"Wrong Choice!\nEnter your choice again\n\n\n";   
     }
     if(flag=='n'||flag=='N')
     break;
    }
    //creating circular linked list
    if(head!=NULL)
    {
    tail->next=head;
    }
    //detecting the loop
    if(detect_loop())
    cout<<"There is a loop\n";
    else
    cout<<"No loop detcted\n";
    return 0;
}

Check whether the Linked List is a Palindrome or not

Algorithm:

The following method takes O(n) time and O(1) extra space.

1) Get the middle of the linked list.

2) Reverse the second half of the linked list.

3) Check if the first half and second half are identical.

4) Construct the original linked list by reversing the second half again and attaching it back to the first half

Solution:

/*

Problem description

to check whether the given list is

a palindrome or not

submitted by

Arjun Mishra

*/

#include<iostream>

#include<stdlib.h>

using namespace std;

//node structure

struct node

{

       char data;

       node *next;

}*head,*tail,*temp;

//function to push a node into the linked list

void push(char val)

{

     temp=(struct node*)malloc(sizeof(struct node));

     if(!(temp))

     {

      cout<<"memory not available\n";

      return;

     }

     temp->data=val;

     temp->next=NULL;

     //if the node is the very first node

     if(head==NULL)

     {

      head=temp;

      tail=temp;

     }

     else//for other subsequent nodes

     {

      tail->next=temp;

      tail=temp;

     }

}

bool reverseAndCheck(struct node *head,struct node* joint)

{

     if(head==NULL)

     {

                   cout<<"List is Empty!Cannot reverse\n";

                   return true;

     }

     if(head->next==NULL)

     {

                   return true;      

     }

     while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      //checking whether the it is a palindrome or not

      struct node* iterator1,*iterator2;

      iterator1=::head;

      iterator2=head;

      while(iterator1!=NULL&&iterator2!=NULL)

      {

       if(iterator1->data!=iterator2->data)

       {

       //first rearranging the list and then returning false

       while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      joint->next=head;

       return false;

       }

       iterator1=iterator1->next;

       iterator2=iterator2->next;

      }

      //first rearranging the list and then returning true

        while(head!=tail)

     {

      temp=head;

      head=head->next;

      temp->next=tail->next;

      tail->next=temp;                

      }

      temp=head;

      while(temp->next!=NULL)

      temp=temp->next;

      tail=temp;

      joint->next=head;

      return true;

}

struct node* findMidPointer()

{

     temp=head;

     node *temp1;

     temp1=head;

     while(temp!=NULL&&temp->next!=NULL)

     {

     temp1=temp1->next;

     temp=temp->next;

     temp=temp->next;

     }

     return temp1;  

}

bool isPalin()

{

     /*

     logic:

     traversing till half...reversing the other half...

     further matching it with the first half

     time-complexity=O(n)

     space-complexity=O(1)

     */

     node *mid,*temp2;

     temp2=findMidPointer();

     mid=temp2->next;

     temp2->next=NULL;

     if(reverseAndCheck(mid,temp2))

     return true;

     else

     return false;

}

void finaltraverse()

{

     if(head==NULL)

     {

                   cout<<"List is empty!\n";

                   return;

     }

     temp=head;

     while(temp!=NULL)

     {

                      cout<<temp->data<<"->";

                      temp=temp->next;

     }

     cout<<"NULL"<<endl;

}

int main()

{

    //let the string be MALAYALAM

    push('M');

    push('A');

    push('L');

    push('A');

    push('Y');

    push('A');

    push('L');

    push('A');

    push('M');

    //checking whether,it's palindrome or not

    if(isPalin())

    {

     cout<<"Yes!it is a palindrome\n";

    }

    else

    {

     cout<<"No!it is not a palindrome\n";

    }

    cout<<"the original list is\n";

    finaltraverse();

    getchar();

    return 0;

}