Find factorial of any number !!

Finding factorial of a number is a requirement that one can come across in many problems. With the limited size of the data types in the high level languages, it is impossible to store these factorial values in a single variable of a particluar datatype. For example the value of 100! is 181 digits long and we certainly got no data type to store such a large value...

So here's how to find factorial of any given number., say 100
We create an array of 100000 digits(just to fit in factorial of bigger numbers) dynamically since its essential to pick up this memory from heap. Then, create a loop which decrements the value by 1 each time and multiplies the result by the decreased value. Following this way, after 100 iterations we finally get the factorial of 500 in an array of size 181. Considering that every element is an integer, the total space required to store this result would be 181*4= 724 bytes.

The source code is as follows :


// factorial of positive integers :

#include
#include
#define M 100000 // defines the size of the array that would store the factorial
using namespace std;

long long *farr=new long long[M];
int counter;

void func(int aindex)
{
    int k=0;
    int findex=0;
    int temp=0;
    int carry=0;
  
    while(k++<=counter)
    {
      temp=farr[findex]*aindex;
      farr[findex++]=(temp+carry)%10;
      carry=(temp+carry)/10;
    }

     findex--;
  
     if(carry)
     {
         if(carry<10)
         {
          findex++;          
          farr[findex]=carry;  
          counter++;
         }
        
         else
           {
                 while(carry)
                 {
                      findex++;      
                      farr[findex]=carry%10;
                      carry/=10;
                      counter++;
                 }  
           }
     }
}


int main()
{
    int h;
    cin>>h;

   for(int i=0;i
    farr[i]=1;
  
    while(h>0)
    {
            func(h);
            h--;
    }
  
    cout<<"result  :  ";
    for(int i=counter;i>=0;i--)
     cout<

   getch();
}

To solve more problems of this kind:
http://projecteuler.net/index.php?section=problems&id=20

An Interesting multiplication method !!!! Figure this out :)

The technique given below is an alternative way to multiply two numbers !!!
its fun trying to figure out how this works....So give it a try :)


A method of multiplying integers using only addition, doubling, and halving.


Method:

1. Take two numbers to be multiplied 
2. In the left-hand column repeatedly halve the last number, discarding any remainders, and write the result below the last in the same column, until you write a value of 1.
3. In the right-hand column repeatedly double the last number and write the result below. stop when you add a result in the same row as where the left hand column shows 1.
4. Examine the table produced and discard any row where the value in the left column is even.
5. Sum the values in the right-hand column that remain to produce the result of multiplying the original two numbers together 

Here's an example...

Multiply: 12 * 13

    Left Col    Right Col

i)   12            13

ii)   6              26

iii)  3              52

iv)  1             104

add the right col numbers corresponding to the left col numbers that are odd.

so adding numbers in row(iii) + row(iv) -> 52+104=156

and thats exactly what 12*13 is...

Try for different numbers..it really works!!!

Figure out the reasoning behind this...should be fun :)

do let me know if you get it :)

A very simple example of Dynamic Programming(DP)

 We all know how to calculate combinations (i.e) nCr.In a very naive approach, in order to calculate say, 10C6, we would apply the following formula to get the result..
nCr= (n)!/(n-r)!(r)!

if suppose you have to calculate combinations of numbers repeatedly in a program, this approach can be very time consuming, so lets do this by dynamic programming... :)
Once the following table is built, we can retrieve combination of any number in O(1) time..
In order to solve it by DP, we gotta follow those two rules as explained in an earlier post..

1) an optimal substructure
we can build a bottom up approach in the following manner,by the formula, nCr=(n-1)Cr + (n-1)C(r-1), 
which implies that in order to calculate factorial of n, if we know factorial of n-1, then nCr can easily be done....so this shows that the final solution is actually build up from various sub problems.
 
2) an overlapping subproblem 
Secondly, the subproblems will be repeated many a times. I shall explain this below in more detail.
So lets solve the problem now...!!!!

let j denote the column values and i denote the row values.
so if j=6, and i=4, so 6C4 = arr[4][6] =15

In the above figure, we can easily find combination of any number till 10.in order to build this table, just follow the following operation, 

for(int i=1;i<=10;i++)

  arr[0][i]=i;

if(i>j)

 arr[i][j]=0;

else

 arr[i][j]=arr[i][j-1]+arr[i-1][j-1];

the statement "arr[i][j]=arr[i][j-1]+arr[i-1][j-1];"shows that all present combinations are acheived from some previous operations.

Work on this example a little more, try it for bigger numbers and I am sure u wil start admiring Dynamic Programming all the more...
 
For any queries, do let me know...

Wats this ??????

well this blog is for...all the programmin enthusiasts & the immensely potential wanna be coders out there !!!!!
 We'll focus on some key programmin concepts nd Data Structures over here...

Lets share our ideas and knowledge

and kick it off here!!!!

Introduction to Dynamic Programming

hi guyz..

Dynamic Programming is easily one of the most crucial topics to master in order to become a good programmer.

In order to effectively take part and achieve in programming competitions, this is one area, we all have to be really gud at, & its pretty simple too, as explained below.

Dynamic programming basically contains 2 elements:

->OPTIMAL SUBSTRUCTURE

a problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems. Whenever a problem exhibits optimal substructure, it is a good clue that dynamic programming might apply.

In dynamic programming, we build an optimal solution to the problem from

optimal solutions to subproblems. Consequently, we must take care to ensure that the range of

subproblems we consider, includes those used in an optimal solution

Optimal substructure varies across problem domains in two ways:

1. how many subproblems are used in an optimal solution to the original problem, and

2. how many choices we have in determining which subproblem(s) to use in an optimal

solution.

Dynamic programming uses optimal substructure in a bottom-up fashion. That is, we first find

optimal solutions to subproblems and, having solved the subproblems, we find an optimal

solution to the problem. Finding an optimal solution to the problem entails making a choice

among subproblems as to which we will use in solving the problem. The cost of the problem

solution is usually the subproblem costs plus a cost that is directly attributable to the choice

itself.

-->OVERLAPPING SUBPROBLEMS:

The second ingredient that an optimization problem must have for dynamic programming to

be applicable is that the space of subproblems must be "small" in the sense that a recursive

algorithm for the problem solves the same subproblems over and over, rather than always

generating new subproblems. Typically, the total number of distinct subproblems is a

polynomial in the input size. When a recursive algorithm revisits the same problem over and

over again, we say that the optimization problem has overlapping subproblems

Dynamic-programming algorithms typically take advantage of overlapping subproblems by solving each subproblem once and then storing thesolution in a table where it can be looked up when needed, using constant time per lookup.