Hello World: Algorithm

Showing posts with label Algorithm. Show all posts

Monday, 2 February 2015

Binary Search Tree Implementation

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / hackerrank / uva / uvalive), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

#include<bits/stdc++.h>
using namespace std;

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

struct BST{
    int data;
    struct BST *left, *right;
}node;

BST *getNewNode()
{
    BST *tmp;
    tmp=(BST *) malloc(sizeof(BST));
    tmp->left=NULL;
    tmp->right=NULL;
return tmp;
}

void insertNode(BST *root, BST *newNode)
{
    //cout<<root->data<<endl;
    if(newNode->data < root->data)
    {
        if(root->left == NULL) root->left=newNode;
        else insertNode(root->left, newNode);
    }
    else
    {
        if(root->right == NULL) root->right=newNode;
        else insertNode(root->right, newNode);
    }
return;
}

void preOrder(BST *root)
{
    cout<<root->data<<" ";
    if(root->left !=NULL) preOrder(root->left);
    if(root->right !=NULL) preOrder(root->right);
return;
}

void inOrder(BST *root)
{
    if(root->left !=NULL) inOrder(root->left);
    cout<<root->data<<" ";
    if(root->right !=NULL) inOrder(root->right);
return;
}

void postOrder(BST *root)
{
    if(root->left !=NULL) postOrder(root->left);
    if(root->right !=NULL) postOrder(root->right);
    cout<<root->data<<" ";
return;
}

BST *searchBST(BST *root, int key)
{
    while(root!=NULL)
    {
        //cout<<root->data<<endl;
        if(root->data == key) return root;
        else if(key < root->data)
        {
            if(root->left != NULL)
                root=root->left;
            else return NULL;
        }
        else if(key > root->data)
        {
            if(root->right !=NULL)
                root = root->right;
            else return NULL;
        }
    }
return NULL;
}

int main()
{
    BST *root, *newNode;
    root = NULL;
    for(int i=0;i<6;i++)
    {
        newNode = getNewNode();
        cin>>newNode->data;
        if(root==NULL) root=newNode; //BST is not initialized.
        else insertNode(root, newNode);
    }
    preOrder(root);
    cout<<"\n";
    inOrder(root);
    cout<<"\n";
    postOrder(root);
    cout<<"\n";

    int searchElement;
    cin>>searchElement;
    //cout<<searchElement<<endl;
    if(searchBST(root, searchElement)==NULL) cout<<"Not found\n";
    else cout<<"found\n";

return 0;
}
/*
5 4 6 3 7 2
9
*/

Monday, 30 June 2014

Multiplication of two huge number

Can we multiply two huge number of more than 1000 digit each?
the numbers are far larger than the range of "long long int".

yes, we can. the idea is pretty simple, Using the Elementary school approach.
for example, we want to multiply ABC with XY. we will store ABC in string num1, and XY in num2.

l1=num1.size(), l2=num2.size();

here, l1 is the number of digit in 1^st string and l2 is the number of digit in 2^nd string.

the approach we were taught in primary school is:

last digit of the result array / string will be CY,

(last-1)^th digit will be BY + CX,

(last-2)^th digit will be AY + BX,

(last-3)^th digit will be AX.

if any digit become larger than 9, then the carry will be added to the previous digit.

initially all digit of result array is 0, we will first add AY, BY, CY to the array, then we will add AX, BX, CX to the array. to optimize the code a little, we will consider the carry operation after all intermediate multiplications.

mx=l1+l2;

note that, the maximum number of digit of the result string is =l1+l2, and the minimum is = l1+l2-1 (if no carry for the first digit)

example: 1000*100 = 100000 & 9999*999=9989001.

int arr[mx], n1[l1], n2[l2];

for(int i=0; i<l1; i++) n1[i]=num1[i]-'0';

for(int i=0; i<l2; i++) n2[i]=num2[i]-'0';

to make calculation easier, we will initialize:

--> an integer array arr[] of length mx for intermediate calculation for result array,

--> an integer array n1[] of l1 length to store the numeric value of ASCII digit of string num1,

--> an integer array n2[] of l2 length to store the numeric value of ASCII digit of string num2.

for(int i=l1-1; i>=0; i--)

for(int j=l2-1; j>=0; j--)

arr[i+j+1]+=n1[i]*n2[j];

this is the main part, consider 0-based index and look the index carefully, after multiplying i^th digit of 1^st string and j^th digit of 2^nd string, we are storing it in (i+j+1)^th digit of result array.

for(int i=mx-1; i>0; i--)

if(arr[i]>9)

{

arr[i-1]+=arr[i]/10;

arr[i]=arr[i]%10;

}

now, the carry operation, from last digit to first digit, if any value of array element is 10 or more, simply add the carry to its left index. look at the condition, why i>0 instead of i>=0? we know the first digit can not have a carry, actually there no problem whether you write i>0 or i>=0.

int pos=0;

while(!arr[pos]) pos++;

the result array may contain leading zeroes, here, pos is the position of first non-zero array index.

string s="";

for(int i=pos;i<mx;i++)

s+=arr[i]+'0';

initialize an empty string, after eliminating of leading zeroes, convert each digit value to ASCII and store it to the string from the first non-zero digit. now s is the result string of multiplication.

Code
Complexity of the code is O(l1*l2)
you will find plenty of problems related to big number multiplication.

Friday, 15 November 2013

Regionals 2000 :: Europe - Central (UVALive 2158 + HDU 1124 + POJ 1401 + ZOJ 2022 + SPOJ FCTRL)

Problem: Factorial
Tutorial: Trailing Zeros of a Factorial
You are given an integer N, you have to print how many Trailing Zeros N Factorial has.

lets be familiar with the term Factorial. Factorial of a number N is the product of all positive integer less than or equal to N.
Example: 5! = 5*4*3*2*1= 120

Trailing Zeros of a number is the total Zeros the number ends with.
Example: Trailing Zero of 120 is 1,
Trailing Zero of 153 is 0,
Trailing Zero of 50300 is 2.

A number will have a trailing zero if the number has 10 as a factor. that means the number should have 2 and 5 as a factor. if we have a pair of 2 & 5, then we can say that it has a trailing zero. so, trailing zero of a number is the minimum of factors of 2 & 5.
wait..
almost all even number has a multiple number of factor 2.
Example: 6! = 6*5*4*3*2*1. has 2 as factors in 2, 4, 6. but there is only one factor of 5 in number 5.
In the factorial of any number, the number of 2′s as factors will always exceed the number of 5′s as factors. that means, there is enough 2's to be paired with 5's.

now, the problem became easier, the total number of 5's as a factor in an integer is the number of trailing zero of that integer. we just need to count the number of 5's as factor of an integer.

if a number is multiple of 5, then it should have at least one 5's as a factor.
if a number is multiple of 25 (5*5), then it should have at least two 5's as a factor.
if a number is multiple of 125 (5*5*5), then it should have at least three 5's as a factor.
and so on...
lets be clear with an example:
the factorial of number 132 has 132/5^1=26 numbers multiple of 5.
132! has 132/5^2=5 (25, 50, 75, 100, 125) numbers multiple of 5^2
132! has 132/5^3=1 (125) numbers multiple of 5^3.
so factorial of 132 has a total 26+5+1=32 factor of 5's.

we are done, number of Trailing Zeros of 132! is 32.
a little simplification for code to avoid pow function is:
Trailing Zero of 132! = 132/5 + (132/5)/5 + ((132/5)/5)/5 = 26 + 5 +1.

Code

Sunday, 20 October 2013

HackerRank October Challenge 2013 Editorial [Angry Children]

Tutorial: Sliding Window / Line Sweeping.
Problem: Angry Children
You have an array of N numbers, You have to pick K numbers where the difference of Maximum element and minimum element are minimized.

Idea: Sliding Window / Line Sweeping.
Straightforward Problem. if you are not familiar with sliding window, you can continue reading.
1st thing comes to your mind is, you should try to take elements with minimum difference to your current element. so, sort the array.
as you already sorted the array, not you can find minimum or maximum element of a segment in O(1), first element of the segment is minimum and last element of the value is maximum. thus difference of the segment can be calculate in O(1).
do a linear scan and minimize the answer. see picture below to be clear how sliding window work.
for N=8, K=3.
and the array after sorting is [1, 2, 7, 7, 17, 18, 20, 22]

here we see, in the 5th iteration we get the minimum value. (taking elements 17, 18 & 20).
so the answer is 3.

Note: this is actually a modification / simplification of original sliding window approach, in this problem you are allowed to sort the array first.

Code:

#include<bits/stdc++.h>

using namespace std;

int main()

{

int arr[100001], k, n;

cin>>n>>k;

for(int i=0; i<n; i++)

cin>>arr[i];

sort(arr, arr+n);

int mn=1e9;

for(int i=0, t=i+k-1; t<n; i++, t++)

mn=min(mn, arr[t]-arr[i]);

cout<<mn<<endl;

return 0;

}