Intersection of 2 Arrays

Given 2 Arrays a1,a2 of length n1 and n2 respectively, Find its Intersection. If there is no intersection print "Intersection does not exist"

Naive Approach:

The naive approach  would be to compare all possible pairs of elements from both arrays and output the ones that match. This would take O(n1*n2).

Better Approach:

• Sort both the arrays
• Take two indexes pointing to start of both arrays.
• Now start comparing elements of both the array till either of indexes reaches the end.
• If 2 elements are equal, increments both the indexes.
• Otherwise increment the index whose array element has less value.

Complexity is O(n1logn1 +n2logn2  +n1+n2) = O(nlogn)

Input:       Two  integer arrays a1 and a2  of different sizes n1 and n2 respectively.

Output:     Elements that appear in both a1 and a2
Example:  For input a1 = {3,6,7,11,9} and b1 = {4,5,6,9,3,11}                 
                 Output should be {3,6,9,11}

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> Intersection ( int *a1,int *a2,int n1,int n2 )
{
    vector<int> v;
    int i=0,j=0;
    sort ( a1,a1+n1 );  // O(n1logn1) complexity
    sort ( a2,a2+n2 );
    while ( i<n1&&j<n2 )
    {
        if ( a1[i]==a2[j] )
        {
            v.push_back ( a1[i] );
            i++,j++;
        }
        else
            if ( a1[i]>a2[j] )
            {
                j++;
            }
            else {
                i++;
            }

    }
    return v;
}
int main()
{
    int n1,n2;
    cin>>n1>>n2;
    int *a1=new int[n1];
    int *a2=new int[n2];
    for ( int i=0; i<n1; i++ )
    {
        cin>>a1[i];
    }
    for ( int i=0; i<n2; i++ )
    {
        cin>>a2[i];
    }
    vector<int> res=Intersection ( a1,a2,n1,n2 );
    if ( res.size() ==0 ) {
        cout<<"Intersection does not exist";
    }
    else
    {
        for ( vector<int>::iterator i=res.begin(); i!=res.end(); i++ )
        {
            cout<<*i<<" ";
        }
    }
    getchar();


}

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

Find nth Element from last in a Single Linked List

We have to find nth element from last in a given linked list. Below is the algorithm used for the same

• Take 2 pointers both pointing to head of linked list.
• Move the first pointer to next element n number of times.
• Now Start moving the second pointer till first pointer reaches end of linked list.
• The data in the node of second pointer is your nth element from last.

See  FindFromLast function for implementation of algorithm.

Input:     number of elements in Linked List
              values in number of elements
              n
Output : nth element from last

For Example:

Input:    7
             3 9 4 13 11 7 2
             4

Output  13



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


    }
    else
    {
        Node *q=NULL;
        q=new Node;
        q->data=data;
        q->next=head;
        return q;
    }
}
int FindFromLast ( Node *head,int n )
{
    int i=n,j=1;
    Node *p=head,*q=head;
    while ( j<=n )
    {

        p=p->next;
        j++;
    }
    while ( p!=NULL )
    {
        q=q->next;
        p=p->next;
    }
    return q->data;
}
int main()
{
    Node *start=NULL;
    int n,input,data;
    cin>>input;
    for ( int i=1; i<=input; i++ )
    {
        cin>> data;
        start=Insert ( start,data );
    }
    cin>>n;
    if ( n>input ||n<=0 )
    {
        cout<<"Enter a number less than total elements and greater than zero";
    }
    else
    {
        cout<<FindFromLast ( start,n );
    }

}

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

Well Order Numbers of Given Length in C++

A number is called Well Order if every digit is greater than previous one(Eg: 238 is well Order as 2<3<8 but 132 is not). Given length of a number, Find all well ordered numbers of Given Length

Input:  Length of number
Output : Well Ordered numbers of given length



#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int p;
void PrintNum ( int prefix,int s, int n )
{
    if ( n==0 && prefix>=pow ( 10.0, p-1 ) )
    {
        cout<< prefix<<"\n";
    }
    else
    {
        for ( int i=s; i<10; i++ )
        {
            PrintNum ( 10*prefix+i, i+1, n-1 );
        }
    }
}
int main()
{
    cin>>p;
    PrintNum ( 0,0,p );
    getchar();

}

Please comment if you find anything incorrect or have any inputs to improve the code.