Lowest Common Ancestor

#include<stdio.h>

struct Node
{
    int data;
    Node *left;
    Node *right;
};
int LCA ( Node* head,int n1,int n2 )
{
    if ( head==NULL )
    {
        return 0;
    }
    if ( head->data<n1 && head->data <n2 )
    {
        return LCA ( head->right, n1, n2 ) ;
    }
    if ( head->data>n1 && head->data >n2 )

    {
        return  LCA ( head->left, n1, n2 ) ;
    }
    return head->data;

}
struct Node* newNode ( int data )
{
    struct Node* node = new  Node ;
    node->data  = data;
    node->left  = node->right = NULL;
    return ( node );
}

int main()
{
 
    struct Node *root        = newNode ( 20 );
    root->left               = newNode ( 8 );
    root->right              = newNode ( 22 );
    root->left->left         = newNode ( 4 );
    root->left->right        = newNode ( 12 );
    root->left->right->left  = newNode ( 10 );
    root->left->right->right = newNode ( 14 );

    int n1 = 10, n2 = 14;

    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    n1 = 14, n2 = 8;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2,LCA ( root, n1, n2 ) );

    n1 = 10, n2 = 22;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    getchar();
    return 0;
}

Find GCD using Euclidean Algorithm

#include<iostream>
using namespace std;

void GcdFinder ( int a,int b )

{

    while ( a!=b )
  {
        if ( a>b ) {
            a=a-b;
        }
        else {
            b=b-a;
        }

    }
    cout<<"GCD Of two numbers is "<<a<<endl;
}
int main()
{
    int a,b;
    cout<<"Enter two numbers\n";
    cin>>a>>b;
    GcdFinder ( a,b );
    getchar();
    return 0;
}

Reverse a Linked List

Reverse a given Linked List.

Implementation
 #include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
void Insert ( Node **head,int d )
{
    if ( head==NULL )
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=NULL;
        *head=newNode;
    }
    else
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=*head;
        *head = newNode;

    }
}
void Display ( Node *head )
{
    while ( head!=NULL )
    {
        if ( head->next!=NULL )
        {
            cout<<head->data<<"->";
        }
        else {
            cout<<head->data;
        }
        head=head->next;

    }
}

Node * ReverseLinkedList ( Node **head )
{
    Node *p,*q,*r;
    p=*head;
    q= ( *head )->next;
    p->next=NULL;
    while ( q!=NULL )
    {
        r=q->next;
        q->next=p;
        p=q;
        q=r;
    }
    *head=p;
    return *head;

}

int main()
{
    Node *head=NULL;
    Insert ( &head,5 );
    Insert ( &head,25 );
    Insert ( &head,35 );
    Insert ( &head,15 );
    Insert ( &head,20 );
    Insert ( &head,2 );
    Display ( head );
    ReverseLinkedList ( &head );
    cout<<"\n";
    Display ( head );
    getchar();

}

Please comment if you find anything incorrect.

Given a Sorted Linked List, Insert a new element in Sorted Way

Given a sorted Linked List, make sure new element is inserted in sorted way 

Algorithm Used 

1. If Linked list is empty then make the node as head and return it.
2. If value of the node to be inserted is smaller than or equal to value of head node then insert the node at start and make it head. 
3. In a loop, find the appropriate node after which the input data is to be inserted. To find the appropriate node start from head, keep moving until you reach a node who's value is greater than the input node.
4. Insert the node  after the appropriate node found in step 3.

For Example:

Below 15 is to be inserted in sorted linked list.

 

#include <iostream>
using namespace std;
struct Node
{
    Node * next;
    int data;
};
void Insert ( Node **start,int d )
{
    Node *cur;
    if ( ( *start ) ==NULL || ( *start )->data>=d )
    {
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next=*start;
        ( *start ) =newNode;

    }
    else
    {
        cur=*start;
        while ( cur->next!=NULL&& ( cur )->next->data<=d )
        {
            cur= ( cur )->next;

        }
        Node *newNode=new Node;
        newNode->data=d;
        newNode->next= cur->next;
        cur->next= newNode;


    }
}
void Display ( Node *start )
{
    while ( start!=NULL )
    {
        if ( start->next!=NULL ) {
            cout<<start->data<<"->";
        }
        else {
            cout<<start->data;
        }

        start=start->next;
    }
}

int main()
{
    Node *start=NULL;
    Insert ( &start,35 );
    Insert ( &start,20 );
    Insert ( &start,10 );
    Insert ( &start,25 );
    Insert ( &start,15 );
    Display ( start );
    getchar();

}

Please comment if you find anything incorrect.

Reference:

1. http://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/

Round off a floating point number to nearest integer

Given a floating point number , convert it nearest integer. 

Approach
Check if floating number is positive, add 0.5 to it otherwise subtract 0.5. For Example if input is -6.8 output will be  -7 , if input is 7.5 output will be 8
Input:       A floating point number.

Output:    Nearest integer

#include <iostream>

using namespace std;
int round_float ( float r )
{
    return ( r > 0.0 ) ? ( r + 0.5 ) : ( r - 0.5 );
}
int main()
{
    float f;
    cin>>f;
    cout<<round_float ( f );
    getchar();

}

Please comment if you find anything incorrect or have any other inputs

Count Number of bits to be flipped to convert one integer to another

One of the approaches to solve this problem is to simultaneously go through bits of two integers and updating the count of bits that are different but better way is to solve it using XOR functionality.

Approach

• XOR both integers
• Count the number of set bits in resultant integer
  

For Eg : 40 in binary is 101000 and 61 is 111101 , then number of bit swap required is 3
Input   :Two integers
Output: Number of bits to be flipped

#include <iostream>
int main()
{
    int firstInteger,secondInteger,res,flip=0;
    std::cin>>firstInteger>>secondInteger;
    res=firstInteger^secondInteger;
    while ( res>0 )
    {
        if ( res&1==1 )
        {
   flip++;
  }
  res >>=1;
    }
 std::cout<<flip;
 getchar();

}



Please comment if you find anything incorrect.

Just for Knowledge

1. A thin client (sometimes also called a lean, zero or slim client) is a computer or a computer program that depends heavily on some other computer (its server) to fulfill its computational roles
2. Thin clients occur as components of a broader computer infrastructure, where many clients share their computations with the same server. As such, thin client infrastructures can be viewed as providing some computing service via several user interfaces. This is desirable in contexts where individual fat clients have much more functionality or power than the infrastructure requires.
3. A fat client  is a computer designed to take on these roles by itself. 
4. Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!
5. A number is Fibonacci if and only if one or both of (5*n² + 4) or (5*n² – 4) is a perfect square.
6. Bi-endian processors can run in both modes little and big endian.
7. Intel based processors are little endians. ARM processors were little endians. Current generation ARM processors are bi-endian. Motorola 68K processors are big endians. PowerPC (by Motorola) and SPARK (by Sun) processors were big endian. Current version of these processors are bi-endians.
8. File formats which have 1 byte as a basic unit are independent of endianness e..g., ASCII files . Other file formats use some fixed endianness forrmat e.g, JPEG files are stored in big endian format.
9. Endianness matters in network programming: Suppose you write integers to file on a little endian machine and you transfer this file to a big endian machine. Unless there is little andian to big endian transformation, big endian machine will read the file in reverse order. You can find such a practical example here. Standard byte order for networks is big endian, also known as network byte order. Before transferring data on network, data is first converted to network byte order (big endian).
10. There are so many variants of Unix like Fedora Core , SUSE Linux etc. To standardize the Unix OS , IEEE has created a standard called Portable Operating System Interface(POSIX).