Wednesday, June 19, 2013

Implementing fibonacci series algorithm C++

Code below gives the recursive implementation of Fibonacci series algorithm.
The method Fibonacci finds the Fibonacci for the given number and we have printed out the Fibonacci series for the given number using the for loop in main method.


//Print the Fibonacci series

#include <iostream>
using namespace std;

int Fibonacci( int num )
{
    if (num <= 0 )
    {
        return 0;
    }

    if (num == 1 )
    {
        return 1;
    }

    return
(Fibonacci(num - 1) + Fibonacci(num - 2));
}

int _tmain(int argc, _TCHAR* argv[])
{
    int num = 10;
    //cin >> num;
    for(  int i = 0; i <= num; i++ )
    {
        cout << " " <<
Fibonacci(i) ;
    }
    cout << endl;
    return 0;

The out put of above method will be as below for  10 as input value. 


 0 1 1 2 3 5 8 13 21 34 55

Tuesday, June 18, 2013

Check if the sub string exist in the target string : C++ code

Function below gives checks if the given sub string exists in the target string and prints the index of sub string.  


//Check if the given sub string exists in the string

#include <iostream>
using namespace std;

bool CheckIfSubStringMatches(char * pStr, char * pSubStr)
{
    while( ('\0' != *pSubStr) && ('\0' != *pStr) )
    {
        if( *pSubStr != *pStr )
            break;
        pSubStr++;
        pStr++;
    }

    if( '\0' == *pSubStr )
    {
        return true;
    }

    return false;
}

void SearchSubstring( char* pBigString, char* pSubstring)
{
    if( NULL == pBigString )
    {
        cout<< "Invalid string entered. None found" << endl;
        return;
    }

    if( NULL == pSubstring )
    {
        cout << "Invalid sub string to search." << endl;
        return;
    }

    if( strlen(pBigString) < strlen(pSubstring) )
    {
        cout << "None found " << endl;
        return;
    }

    char * pStr = pBigString;
    char * pSubStr = pSubstring;
    int index = 0;

    while( '\0' != *pStr )
    {
        if( *pStr == *pSubStr)
        {
            if( CheckIfSubStringMatches(++pStr, ++pSubStr) )
            {
                cout << "Found SubString at Index = " << index << endl;
                return;
            }
            pSubStr = pSubstring;
        }
        else
        {
            pStr++;
        }
        index++;
    }  

    cout << "None found " << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{

    char myStr[4][5] =    {{"This"},
                         {"put."},
                         {"xxxx"},
                         {"g I "}
                      };
    char * string = "This is the string I wanted to input.";
    for( int ctr = 0; ctr < 4; ctr++ )
    {
        SearchSubstring( string, myStr[ctr] );
    }
    return 0;
}

The output of code above is given below

Found SubString at Index = 0
Found SubString at Index = 33
None found
Found SubString at Index = 17

Monday, June 17, 2013

Move spaces from string to start of the string

We can move the spaces from given string at start easily, if we traverse the string from end. Whenever we encounter space while traversing the string from end just copy next character at the location of space and go on copying rest characters in the same fashion. This method take two iteration, one for finding out the end of string second to move the space.

Method MoveSpacesAtStart does the same. It first finds out the end of string and then starts searching spaces back words. This method maintains the character sequence except for the spaces, if we were allowed to alter the character sequence this can be done with single iteration as well.


//Method for moving all spaces from the string at start using only two iterations of the string
#include <iostream>
using namespace std;

void MoveSpacesAtStart( char * inputString )
{
    if ( NULL == inputString )
    {
        return;
    }

    cout << "Before : " << endl << inputString << endl;
    char * end = inputString;
    char * temp = NULL;
    while( *(end + 1) != '\0' )
    {
        end++;
    }

    temp = end;
    int spacecounter = 0;
    while( end != inputString )
    {
        if( *end == ' ' )
        {
            spacecounter++;
        }
        else
        {
            *temp = *(temp - spacecounter);
            temp--;
        }
        end--;
    }

    *temp = *(temp - spacecounter);
    temp--;

    while( temp != inputString)
    {
        *temp = ' ';
        temp--;
    }

    *temp = ' ';

    cout << "After: " << endl << inputString << endl << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    char myStr[4][38] =    {{"This is the string I wanted to input."},
                         {"        the string I wanted to input."},
                         {"This is the string.                  "},
                         {"T i i s t e s r n  I w nt d to i p t."}
                      };
    for( int ctr = 0; ctr < 4; ctr++ )
        MoveSpacesFromEnd( myStr[ctr] );  
    return 0;
}

Out put of the above program is shown below


Before :
This is the string I wanted to input.
After:
       ThisisthestringIwantedtoinput.

Before :
        the string I wanted to input.
After:
             thestringIwantedtoinput.

Before :
This is the string.
After:
                     Thisisthestring.

Before :
T i i s t e s r n  I w nt d to i p t.
After:
                 TiistesrnIwntdtoipt.

Sunday, June 16, 2013

Finding the majority number from given array : Moore's majority Voting algorithm

Majority number in a given sequence of numbers is a number that occurs more than N/2 times where N is the count of numbers in the sequence. We can find the majority number in multiple ways.
  1. Brute force method: Have two nested loops which will calculate of maximum count of each elements then compare which element appears maximum time in array from stored count, then check if its count exceeds N/2. Time complexity : O(N*N)
  2. Using Hash Map as temporary storage: Traverse array once, while traversing through array keep count of each element in the hash map with element from array as key and its count as value. Then traverse through map to find out which is maximum occurring element. Time complexity : O(NlogN) and space complexity O(N)
  3. Using Moore’s Voting Algorithm:  First iterate through array to find out if array contains the majority number. In second iteration confirm if its majority number. Below is the code for finding majority number using Moore's voting algorithm.
//Code to find out majority number present in the given array using Moore's Voting algorithm  

#include <iostream>
using namespace std;

void MajorityNumber( int * input, int size )
{
    if( size <= 0 )
    {
        cout << "NONE" << endl;
        return;
    }

    if ( NULL == input )
    {
        cout << "NONE" << endl;
        return;
    }

    if( size == 1 )
    {
        cout << "Majority Number : " << input[0] << endl;
        return;
    }

    int nCurrent = input[0];
    int nCounter = 1;

    for( int nIterator = 1; nIterator < size; nIterator++ )
    {
        if( input[nIterator] == nCurrent )
        {
            nCounter++;
        }
        else
        {
            nCounter--;
            if(nCounter == 0 )
            {
                nCounter = 1;
                nCurrent = input[nIterator];
            }
        }
    }

    if( nCounter <= 0)
    {
        cout << "NONE" << endl;
        return;
    }

    nCounter = 0;

    for( int i = 0; i < size; i++)
    {
        if( input[i] == nCurrent )
        {
            nCounter++;
        }
    }

    if( nCounter > (size/2) )
    {
        cout << "Majority Number: " << nCurrent << endl;
        return;
    }

    cout << "NONE" << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    int arrays[4][9] = {
                        {9, 8, 8, 9, 3, 8, 6, 8, 8 },
                        {17,17,11,17, 11, 11, 11, 17, 17},
                        {11,11,8,8, 8, 11, 11, 11,8},
                        {10,10,10, 11, 11, 11, 11, 11, 10}
                     };

  
    for( int i =0; i < 4; i++)
    {
        MajorityNumber( arrays[i], 9 );
    }
    return 0;
}

Above method loops through each element and maintains a count of current element, If the next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the current element to the next element and sets count to 1. Out put of above code will be as below.


NONE
Majority Element : 17
Majority Element : 11
Majority Element : 11

Saturday, June 1, 2013

Find nth max last element from unsorted array

We have to find out the nth last max element from the unsorted array. We can solve this problem in multiple ways. We will check some of the ways of doing this.
  • Sort last n elements from the input array in descendent order. We can use the similar method as selection sort for sorting last n elements. Method ReturnNthLastElementUsingSelection gives code for this approach.  
 
int ReturnNthLastElementUsingSelection( int * array, int nSize, int nThLast)
{
    if( NULL == array )
        return -1 ;
  
    if( nSize < nThLast )
        return -1;

    int nCurrentMax = -1;
    for( int nIterator = 0; nIterator < nThLast; nIterator++)
    {
        nCurrentMax = array[nIterator];
        int nPos = nIterator;
        for( int nTemp = nIterator +1; nTemp < nSize; nTemp++ )
        {
            if( nCurrentMax < array[ nTemp ] )
            {
                nCurrentMax = array[ nTemp ];
                nPos = nTemp;
            }
        }

        array[nPos] = array[ nIterator ];
        array[nIterator] = nCurrentMax;
    }

    return nCurrentMax;
}
  • If we don't want to modify the given array we can solve this problem with some temporary space by creating the Map which will store our n last max elements. Map is used as a searching would be faster in the map for already added max element.
int ReturnNthLastElementWithTempSpace( int * input, int size, int nThLast)
{
    if ( NULL == input )
        return -1;

    if( size < nThLast )
        return -1;

    int nThMax = 0;

    std::map<int, bool> MaxElementIndexMap;
    
    for( int nFinder = 0; nFinder < nThLast; nFinder++ )
    {
        int pos = 0;
        nThMax = -1;

        for( int nIterator = 0; nIterator < size; nIterator++)
        {
            if( nThMax < input[nIterator] )
            {
                if( MaxElementIndexMap.find(nIterator) == MaxElementIndexMap.end() )
                {
                    nThMax = input[nIterator];
                    pos = nIterator;
                }
            }
        }

        MaxElementIndexMap.insert( std::map<int, bool>::value_type(pos, true));
    }

    return nThMax;
}

Thursday, May 30, 2013

Find two elements in array having sum equal to given element

We can use insertion sort method to find the two element from the array having sum same as given element. Method FindSum displays two elements from array having sum same as given element.

void FindSum( int * a, int size, int Sum)
{
    int firstNum = 0, secondNum = -1;
    for(; firstNum < size; firstNum++)
    {
        int sercahKey = Sum - a[firstNum];
        for( int i = firstNum + 1; i < size; i++)
        {
            if( sercahKey == a[i] )
            {
                secondNum = i;
                break;
            }
        }
        if( secondNum != -1 )
            break;
    }
    if( secondNum == -1 )
        cout << "Could not found two number having sum " << Sum << endl;
    else
        cout << "found two number having sum [" << Sum  << "] as [ " << a[firstNum] << "] and [" << a[secondNum] << "]."  << endl;

}


The above method requires o(n2) time complexity. Using map the time complexity can be reduced to o(n) as shown in below method.


void FindPairMatchingSum(int * arr,  int size, int sum)
{

    map<int, int> mapOfArray;
    for (int i = 0; i < size; i++)
    {
        mapOfArray.insert(make_pair(arr[i], i));
    }

    for (int  i = 0; i <size; i++)
    {
        int key = sum - arr[i];
        map<int, int>::const_iterator kit = mapOfArray.find(key);
        if (kit != mapOfArray.end())
        {
            cout << "Found Pair at index : " << i  << "  & " << kit->second;
            break;
        }
    }
}

Implementing Selection Sort Algorithm in C++/C

SelectionSort method implements Selection Sort algorithm in the simplest way. This method you can use in C/C++ program. Method takes integer array and size the array to be sorted and sorts the array in place.
 

void SelectionSort(int * array, int nSize)
{
    if( NULL == array )
        return;
  
    if( nSize < 1 )
        return;

    for( int nIterator = 0; nIterator < nSize - 1; nIterator++)
    {
        int nCurrentLow = array[nIterator];
        int nPos = nIterator;
        for( int nTemp = nIterator +1; nTemp < nSize; nTemp++ )
        {
            if( nCurrentLow > array[ nTemp ] )
            {
                nCurrentLow = array[ nTemp ];
                nPos = nTemp;
            }
        }

        array[nPos] = array[ nIterator ];
        array[nIterator] = nCurrentLow;
    }
}