Friday, May 31, 2013

How does Bubble sort works?

Bubble sort is a comparison based sorting algorithm. It works like following. 
We perform series of iterations to 'bubble up' the elements one by one so that they form a sorted order. For example we have to sort an array [3,1,4,5,2] in ascending order, In the first iteration, the element 5 will be bubbled up to the last spot. In the second iteration element '4' will be moved to the last but first spot and so on. The following sequence shows one iteration. In each step in the iteration, successive pairs of elements are compared, if they violate the order, swap it. 

3<->1 4 5 2 
1 3<->4 5 2 
1 3 4<->5 2 
1 3 4 5<->2 
1 3 4 2 5 

This iteration is repeated until the entire array is sorted. In the first iteration, there will be n-1 comparisons. In the second iteration there will be n-2 comparisons. The number of comparisons decreases with each iteration. The last iteration will have only one comparison. The following code shows the implementation of the above approach. The time complexity of bubble sort is O(n^2).
 
#include <iostream>
using namespace std;

//helper method to swap two elements
void swap( int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}
//bubble sort function, takes array and it's size
//as parameters
void bubble_sort(int *array, int n)
{
 int i,j;
 //outer loop runs for n-1 iterations
 for( i = 0 ; i < n-1 ; i++)
 {
  //inner loop is for comparisons
  //in each iteration comparisons reduce by 1
  for( j = 0 ; j < n-1-i ; j++)
  {
   //if elements are out-of-order, swap them
   if( array[j] > array[j+1] )
    swap(array[j], array[j+1]);
  }
 }
}
int main()
{
 int n;
 cin>>n;
 int *array = new int[n];
 int i;
 for( i = 0 ; i < n ; i++ )
 {
  cin>>array[i];
 }
 bubble_sort(array,n);
 for( i = 0 ; i < n ; i++)
 {
  cout<<array[i]<<" ";
 }
 return 0;
}
 
In bubble sort there is a mechanism to detect if the input array is already sorted. In any iteration, if there are no swappings performed, then we can conclude that the array is sorted. Here is how we can modify the bubble sort to implement this. 


void bubble_sort(int *array, int n)
{
 int i,j;
 bool swap_flag = false;
 //outer loop runs for n-1 iterations
 for( i = 0 ; i < n-1 ; i++)
 {
  //inner loop is for comparisions
  //in each iteration the comparisions count reduce by 1
  for( j = 0 ; j < n-1-i ; j++)
  {
   //if elements are out-of-order, swap them
   if( array[j] > array[j+1] )
   {
    swap(array[j], array[j+1]);
    swap_flag = true;
   }   
  }
  //if no swaps are performed in the inner loop, break
  if( !swap_flag )
   break;
 }
}

Thursday, May 30, 2013

Program to find GCD of two numbers

In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder - from Wikipedia
For example, the GCD of 8 and 12 is 4
Euclidian method: This is also called division algorithm. Take smallest of the two numbers and divide the other number. If the remainder is zero smaller number is the GCD. Otherwise replace the smaller number with remainder, and bigger number with present smaller number and repeat the same procedure.

Here is the step-by-step calculation


8)12(1
   8
 ----
   4)8(2
     8
    ---
     0


The following c++ code implements the iterative and recursive version of Euclidian algorithm.



#include <iostream>

using namespace std;
void swap(int &x, int &y)
{
 int temp = x;
 x = y;
 y = temp;
}
//iterative version of Euclidian algorithm
int gcd(int x,int y)
{
 while ( (y % x) != 0)
 {
  int r = y % x;
  y = x;
  x = r;
 }
 return x;
}
//recursive version of Euclidian algorithm
int gcd_recursive(int x, int y)
{
 if( y % x == 0)
  return x;
 return gcd_recursive( y%x, x);
}

int main()
{
 int x,y;
 //read two numbers
 cin>>x>>y;
 //both iterative and recursive versions requires first parameter <= second
 //swap if firt is greater
 if( x > y )
 {
  swap(x,y);
 } 
 cout<<"GCD(" << x << "," << y << ")=" << gcd_recursive(x,y) << endl;
 return 0;
}

Friday, May 24, 2013

Finding the length of a linked list

In this post we will see an algorithm to find the length of the linked list. Here singly linked list is implemented in Object Oriented Programming (OOP) paradigm in C++. The algorithm is very simple. Just start at the beginning of the linked list, move to next until you reach the end of the list, incrementing a counter in each iteration. Following is the source C++ code for the same.


#include <iostream>

using namespace std;

//Node definition for a single linked list
class SLLNode
{
 private:
  //data member
  int data;
  //pointer to next node in the linked list
  SLLNode *nextPtr;
 
 public:
  
  //Single argument constructor
  //initializes data with d, next pointer to NULL
  SLLNode(int d):data(d),nextPtr(NULL)
  {
  }
  //to initialize both members
  SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
  {   
  }
  //returns the data
  int getData()
  {
   return data;
  }
  //sets the data
  void setData(int d)
  {
   this->data = d;
  }
  //gets the next pointer
  SLLNode* getNext()
  {
   return this->nextPtr;
  }
  //sets the next pointer
  void setNext(SLLNode *ptr)
  {
   this->nextPtr = ptr;
  }
};

//defines the actual single linked list
class SinglyLinkedList
{
 private:
  //maintain two pointers to the start and the end
  //so that we can append at the end easily (constant time complexity)
  SLLNode * head;
  SLLNode * tail;
 public:
  SinglyLinkedList()
  {
   head = NULL;
   tail = NULL;
  }
  //adds the node to the end of the list
  void appendNode(SLLNode* ptr)
  {
   //check if list is empty
   if( head == NULL)
   {
    //update both the pointers
    head = tail = ptr;
   }
   else //simply append at the end, and move the tail pointer
   {
    tail->setNext(ptr);
    tail = tail->getNext();
   }
  }
  //gets the length of the list
  int getLength()
  {
   int length = 0;
   
   SLLNode* ptr = head;
   
   while ( ptr != NULL )
   {
    length++;
    ptr = ptr->getNext();
   }
   return length;
  }
};

int main()
{
 SinglyLinkedList list;
 list.appendNode(new SLLNode(1));
 list.appendNode(new SLLNode(2));
 list.appendNode(new SLLNode(3));
 list.appendNode(new SLLNode(4));
 cout<<"Length: "<<list.getLength()<<endl;
 return 0;
}

Thursday, May 23, 2013

Member initialization list in C++

You all know that in C++, constructors are used to create an object. We normally initialize all the data members with some valid data in the constructor. We generally write code similar to the following and think that m_data variable is being initialized where as it is actually being assigned.

class MyClass
{
 public:
  Myclass(int d)
  {
   m_data = d;
  }
 private:
  int m_data;
}
 

To actually initialize a data member, we need to use member initialization list in C++. Using member initialization list, the constructor is written as follows

class MyClass
{
 public:
  Myclass(int d):m_data(d)
  {
  }
 private:
  int m_data;
}
 

Here we specified the member initialization list after constructor name followed by colon (:) If multiple members are present, they are separated by Comma. like m_data1(d1), m_data2(d2). In this case the members are initialized before entering the constructor itself.

What happens in the first case?  The default constructor (that is provided by the compiler) is called to initialize non-primitive data types before entering the written constructor. All the primitive type data members like int, char, float are not guaranteed to get initialized in the default constructor.

Wednesday, May 22, 2013

Finding the missing element in an array:

An array of size (n-1) contains all the numbers in the range [1..n] except one number which is missing. Write a program to find the missing number in O(n) time and O(1) space.

For example let N= 5 and the input array is [1,3,4,5], the output should be 2.

Given O(n) space we can always maintain a boolean array of size n to store a flag for each number if it is present or not. Here the restriction is to use constant extra space.

Two methods are discussed here.

Method#1:
Find sum of all the elements in given array. Let it be sum1. Find the sum of numbers from 1 to n. It would be
n*(n+1)/2 (remember Arithmetic Progression from your school mathematics?) let it be sum2. Now subtracting sum1 from sum2 ( sum2-sum1) gives the required result.
Method#2:
Find XOR of all the elements in the array, let it be ax. Find XOR of elements from
[1..n], let it be nx. Then performing XOR between these two gives the missing number

The following C++ code shows the implementation of both the methods stated above. Both algorithms run in O(n) time and O(1) space complexity.





#include <iostream>
using namespace std;
//array contains n-1 numbers, this method finds
//the nth number missing.
int findMissingNum(int *array, int n)
{
 //sum of first n numbers 1...n
 int nSum = n*(n+1)/2;
 //find array sum
 int arSum = 0;
 for( int i = 0 ; i < n-1 ; i++)
 {
  arSum += array[i];
 }
 // difference between two sum, gives the missing number
 return nSum - arSum;
}

int findMissingNumXor(int *array,int n)
{
 int nXor; //XOR of 1..N elements
 int arXor; //XOR of array elements
 int i;
 //find XOR of 1 to n elements
 for( i = 0 ; i < n ;i++)
 {
  nXor = nXor ^ (i+1);
 }
 //find XOR of array elements
 for( i = 0 ; i < n-1 ; i++)
 {
  arXor = arXor ^array[i];
 }
 //XOR of two gives the result
 return nXor ^arXor;
}
int main()
{
 int *array;
 int n;
 cin>>n;
 //allocate memory for n-1 numbers
 array = new int[n-1];
 int i;
 //read n-1 numbers as input
 for( i = 0; i < n-1; i++)
 {
  cin>>array[i];  
 }
 
 cout<<findMissingNumXor(array,n);
 //deallocate dynamic memory
 delete[] array;
 return 0;
}

Friday, May 17, 2013

Couple elimination problem

Given a string of some symbols, write a program to transform a string by repeatedly eliminating two same symbols occurring together.
For example if the input string is 'RGGB' it will be reduced to 'RB' because 'GG' can be eliminated.

Here are some more examples of input - output

Input   | Output
-------------------
GBRRBR  | GR
BGRGRR  | BGRG
GGBB    | <empty>
RGBGBR  | RGBGBR


Here is how we can solve this problem. Add each character into a temporary array. As you insert the character, check for previously inserted character. If it is same, erase that character otherwise add it to the temporary array. At the end, the temporary array has the transformed string.

C++ implementation of the above approach is given below.

 
#include <iostream>
#define MAX 100
using namespace std;

int main()
{
 char string[MAX];
 char temp[MAX];
 
 cin>>string;
 int i;
 int tempInd = 0; //to track temp string
 
 for( i = 0 ; string[i] != '\0' ; i++)
 {
  //If temp string has atleast one character
  if( tempInd > 0)
  {
   //If previous, and current chars are same, erase
   if( temp[tempInd-1] == string[i] )
   {
    tempInd--;
   }
   else//not same, append the char to temp
   {
    temp[tempInd++] = string[i];
   }
  }
  else //temp is empty, simply append the character
  {
   temp[tempInd++] = string[i];
  } 
 }
 //append the NULL character at the end
 temp[tempInd] = '\0';
 //print the transformed string
 cout<<temp<<endl;
 return 0;
}

Wednesday, May 15, 2013

Replacing spaces in a character array with %20

Given a character array which contains some spaces. we have to replace all the spaces with the string '%20'. This algorithm is commonly used during HTML encoding of the URLs in the web browsers. Assume that the array has enough space at the end to accommodate the expanded string, how do we do this efficiently?

The following solution uses no extra space and runs in O(n) time. The trick here is to start copying the characters from the end, and wherever we find space replace it with '%20'. The following C++ code does exactly that.



#include <iostream>
#define MAX 100
using namespace std;

void replaceSpace(char *array)
{
 int len=0,i;
 int spaceCount = 0;
 //this loop calculates the spaces and length of the string
 for( i = 0 ; array[i] != '\0' ; i++ )
 {
  //count spaces
  if( array[i] == ' ')
   spaceCount++;
  //update length
  len++;
 }
 //array has enough space, try to copy the string from end
 //end index will be length + 2*no of spaces bcoz for each space
 //there will be (3-1=2) two additional characters inserted
 int resInd = len + 2*spaceCount;
 
 //len is the index of '\0' (i.e last) in the original string
 //start copying from there
 while ( len >= 0)
 {
  //if space, insert %20 in reverse, bcoz we are copying from reverse
  if( array[len] == ' ')
  {
   array[resInd--] = '0';
   array[resInd--] = '2';
   array[resInd--] = '%';  
  }
  else //copy as it is
  {
   array[resInd--] = array[len];
  }
  len--; 
 }
}
int main()
{
 char chArray[MAX];
 gets(chArray);
 replaceSpace(chArray);
 cout<<chArray<<endl;
 return 0;
}

Tuesday, May 14, 2013

Common elements between two sorted arrays

Given two sorted arrays, how do you efficiently find the common elements between those two?

Method#1:
Simple and Brute-force approach
Iterate through one array, and try to find the element in another array using linear search. If it is found, then print it. This approach takes O(n^2) time as for each element in the first array we doing a linear search in the second array which takes O(n). So for n elements it would be O(n^2).

Method#2:
Better approach with binary search
This approach is simliar to the first one except that it uses binary search instead of linear search for finding an element in the second array as the arrays are sorted. Binary search takes O(log n) for each element. So for n elements the time complexity would be O(n log n).

Method#3:
Efficient
This method fully utilizes the fact that both arrays are sorted. Start with two indices pointing to beginning of the arrays. If the elements pointed by these indices are same, then it is a common element, and we advance both the pointers. If one element is smaller, then advance that pointer (in hope of finding the next equal element). Continue this until any one of the two indices reaches their end.

Here is the C++ code which implements the third approach.

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

using namespace std;

//prints the intersection of two sorted arrays
//duplicates are allowed
void printIntersect(vector<int>& s1, vector<int>& s2)
{
 //i and j start 0 i.e first element
 int i = 0 , j= 0;

 //while either of the two indices reaches end
 while ( i < s1.size() && j < s2.size() )
 {
  //if first array element is lesser, advance that index by one
  if( s1[i] < s2[j] )
  {
   i++;
  }
  //otherwise advance second index
  else if( s1[i] > s2[j] )
  {
   j++;
  }
  //both elements are same, print it, and advance both the pointers 
  else
  {
   cout<<s1[i]<<" ";
   i++;
   j++;
  }
 }
}

int main()
{
 vector<int> set1, set2;
 int n1,n2; //size of the sets
 cin>>n1>>n2;

 int i;
 //read two arrays
 for( i = 0 ; i < n1; i++ )
 {
  int d;
  cin>>d;
  set1.push_back(d);
 }
 for( i = 0 ; i < n2; i++ )
 {
  int d;
  cin>>d;
  set2.push_back(d);
 }
 printIntersect(set1,set2);
 return 0;
}

Monday, May 13, 2013

Rotating an array

Rotating an array:

In this post we will discuss two solutions for rotating an array by a given number of times. One is a simple solution and another uses the reversal operation (discusses in the previous post).

Method#1: Simple and intuitive

In this method, we will copy the last element into a variable, and shift all the elements right by one step, and copy the stored element into the empty spot created at the beginning of the array. We repeat this for the given number of times.

Method#2: Using reversal algorithm

I have taken this algorithm from here. It is a three step procedure. Let array[0:n-1] be the array, and 's' be the number of times to rotate the array.
step 1: Reverse the sub-array array[0:s-1]
step 2: Reverse the sub-array array[s:n-1]
step 3: Reverse the whole array i.e array[0:n-1]
 

For example let the array be [7 1 2 3 8], and it is to be rotated 3 times
here is how it works
step 1: [2 1 7 3 8]
step 2: [2 1 7 8 3]
step 3: [3 8 7 1 2]


C++ implementation of the above two methods is given below.



#include <iostream>
#include <string>

using namespace std;

//right rotates array of size n by s positions
//assumes that n > 1 (atleast 2 elements) and s < n
void rotateSimple( int* array, int n, int s)
{
 int i;
 int j;
 for( i = 0 ; i < s ; i++ )
 {
  //store the last element
  int last = array[n-1];
  
  //shift all elements right by one
  for( j = n-2 ; j >= 0 ; j-- )
  {
   array[j+1] = array[j];
  }
  //copy stored element to the beginning
  array[0] = last;
 }
}
//helper method for reversal
void swap( int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}

//function to reverse the sub-array array[low to high
void reverseArray(int *array, int low, int high)
{
 while( low < high ) //until both ends meet
 {
  swap( array[low], array[high] ); //swap the elements
  low++; //increment left
  high--;//decrement right
 }
}
//rotate the array using reversal operation
void rotateByReverse(int* array,int n, int s)
{ 
 reverseArray(array,0,s-1);
 reverseArray(array,s,n-1);
 reverseArray(array,0,n-1);
}

//utlity to print the array
void printArray(int * array,int n)
{
 for( int i = 0; i < n; i++ )
 {
  cout<<array[i]<<" ";
 }
 cout<<endl;
}

int main()
{
 int n; //array size
 int s; //rotation count
 //read array size, and rotation count
 cin>>n>>s;
 //dynamically allocate array based on input size
 int *array = new int[n];
 int i;
 for( i = 0 ; i < n; i++ )
 {
  cin>>array[i];
 }
 //call rotate function
 rotateByReverse( array, n, s);
 printArray( array, n);
 //release the memory
 delete[] array;
 return 0;
}

Friday, May 10, 2013

Reversing an array

In this post we will discuss a simple problem on Arrays. Given an array of numbers, how do we reverse it efficiently?

Here is the simple and effective approach. We start with one index pointing to the start, and another index pointing to the end of the array. We swap the two elements at these indices, increment left index, and decrement right index. We continue this procedure until both indices meet each other. Then we stop. At the end, the array is reversed.

For example, let us consider the array with 5 elements, Here is how it works

Array: [1  2  3  4  5] - swap
        |           |
       left       right
      
       [5  2  3  4  1] - swap
           |     |
          left  right
      
       [5  4  3  2  1] - stop
              |
             left
             right


 
#include <iostream>
#include <string>

using namespace std;

void swap( int &a, int &b)
{
 int temp = a;
 a = b;
 b = temp;
}
//function to reverse the array
void reverseArray(int *array, int n)
{
 int low = 0; //initialize low to first element
 int high = n-1; //initialize high 

 while( low < high ) //until both ends meet
 {
  swap( array[low], array[high] ); //swap the elements
  low++; //increment left
  high--;//decrement right
 }
}
void printArray( int *array,int n)
{
 for(int i = 0 ; i < n;i++ )
 {
  cout<<array[i]<<" ";
 }
 cout<<endl;
}
int main()
{
 int n;
 cin>>n;
 int* array = new int[n];
 int i;

 for( i = 0 ; i < n ; i++)
 {
  cin>>array[i];
 }
 reverseArray( array, n);
 printArray( array, n);
 return 0;
}

Wednesday, May 8, 2013

Bracket matching problem

Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example.

Let us consider the following problem. We have a string which contains only '(' and ')' characters. We have to write a program to check if it forms a valid expression.
For example the string "(()())" is a valid expression where as "(()()" and "())" are not.

The algorithm for solving the question goes like this. 


1. For each character in the string
    If the symbol is '('
         push it on to the stack
   else
        If the stack is empty
            return false
       If top of the stack contains '('
            pop off the top element
2. If the stack is empty return true otherwise return false


Here is the program which implements the above algorithm.



#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool isValidExpr(string input)
{
 stack<char> stck;

 for(int i = 0; i < input.length() ; i++)
 {
  char ch = input.at(i);

  if( ch == '(' ) //if open brace, push
  {
   stck.push(ch);
  }
  else //closed brace
  {
   if( stck.empty() )// if stack is empty, there no matching open brace
    return false;
   if ( stck.top() == '(' ) //matching open brace found, so pop
   {
    stck.pop();
   }
  }
 }
 if( stck.empty() )
  return true;
 return false;
}

int main()
{
 string inputExpr;
 cin>>inputExpr;
 if( isValidExpr(inputExpr) )
  cout<<"Valid Expression";
 else
  cout<<"Invalid Expression";
 return 0;
}

Tuesday, May 7, 2013

Counting characters in the given string using C++ STL map

Map is one of the most useful data structure in solving many programming problems. Today we will see how to use C++ STL map with a simple example. Counting the frequency of letters in a given string. The map data structure stores <key,value> pairs. In this example key will be the character, and the value will be it's frequency. Here is the code to do this.

#include <iostream>
#include <string>
#include <map>

using namespace std;

void getFrequency(string strInput,map<char,int> & fMap)
{
 map<char,int>::iterator it; //iterator to find the entries in map
 for(int i = 0 ; i < strInput.length() ; i++ )
 {
  char ch = strInput.at(i);
  it = fMap.find(ch); //find the character in the map
  if( it == fMap.end() ) //if not present in the map
  {
   fMap.insert( make_pair(ch,1) );//add an entry
  }
  else
  {
   it->second++; //else increment the frequency
  }
 }
}

void printFrequency(map<char,int> & fMap)
{
 map<char,int>::iterator it;//iterator to loop through all the chars
 for( it = fMap.begin() ; it != fMap.end() ; ++it )
 {
  cout<<"["<< it->first<<"]"<<"->"<<it->second<<endl;
 }
}

int main()
{
 string strInput;
 //read input string; this implementation does not reed space separated strings
 cin>>strInput;
 map<char,int> frequencyMap; //frequency map
 getFrequency(strInput, frequencyMap); //get the frequencies
 printFrequency(frequencyMap); //print the frequencies
 return 0;
}

Monday, May 6, 2013

Finding count of a number in a sorted array

In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
Given a sorted array of numbers, How to find the frequency of a given number?

Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result. 


C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.
The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

Here is the C++ code.

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

using namespace std;

int getCount(vector<int> & numVector, int d)
{
 int result = 0;
 vector<int>::iterator left, right;
 //find the left-most occurence
 left = lower_bound( numVector.begin(), numVector.end(), d );
 //find right-most occurence only if the number is present
 if( left != numVector.end() )
 {
  right = upper_bound( numVector.begin(), numVector.end(), d );  
  result = right-left; //right points to one element beyond. 
 }
 return result;
}
int main()
{
 int n;
 //read array size
 cin>>n;
 int i,num;
 vector<int> nums;
 //read the array
 for( i = 0 ; i < n ; i++ )
 {
  cin>>num;
  nums.push_back(num);
 }
 //read the number to be counted
 cin>>num;
 cout<<getCount(nums,num);
 return 0;
}

Finding duplicates from given set of numbers

Given a list of numbers. How do we write a program to find the duplicates among them?
A simple algorithm is to compare each possible pair in the list to see if there are any duplicates. But this algorithm runs in O(n2) time.
We can use the following simple algorithm using the set data structure. This data structure supports insert/add, find operations. We read one number at a time and try to find it in the set. If the set already contains that element, we declare that element as a duplicate, otherwise we insert that element into that set. The following is a Java implementation of the same.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.*;
import java.util.HashSet;
/**
 *
 * @author Ravi
 */
public class DuplicateNums {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        try
        {
            //Read from the standard input
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String input = br.readLine();
            String [] strNums = input.split(" ");
            
            //create the hash set to store the unique numbers
            HashSet<Integer> hSet = new HashSet<Integer>();
            
            for( int i = 0 ; i < strNums.length ; i++)
            {
                //try to add the number to the set, 
                //if add method returns false, the number is a duplicate
                if( !hSet.add( Integer.parseInt(strNums[i]) ) )
                {
                    System.out.print(strNums[i] + " ");
                }
            }
            System.out.println();
        }
        catch(IOException ioe)
        {
            System.out.println("Exception while reading the input" + ioe.getMessage());
        }
        catch(NumberFormatException nfe)
        {
            System.out.println("Invalid Input "+ nfe.getMessage());
        }
    }
}

We have used HashSet data structure from the Java standard library. This provides O(1) time for insert and find operations in an average case. So the average time complexity of the above program is O(n). Since we are storing the elements in the set, the space complexity is O(n) in the worst case (No duplicates in the list).