Digits_of_FACTORIAL

[kernelio]

Hi
is there any way to speed up my program ,it needs to find

The first smallest number who's factorial is bigger or equal to the inputed number

first we input the number of test cases

should i use some other data structure than dynamic array

#include <math.h>
#include <stdio.h>
#include <stdlib.h> 

void brojCif(int *a,int n)//it find's number of digits of a factorial of  all numbers from 1 to n
{ 
int i;
float dig=0.0;

        for (i = 1; i <=n; i++)
        {
         dig +=log10(i);
        a[i]=(int)floor(dig)+1;
          }

}

int main()
{  
int i=0,br,t=0,br_cif;    
int *a= (int*)malloc(sizeof(int)*1000000);

scanf("&#37;d",&t);  
brojCif(a,1000000); 
while(t--){
                scanf("%d", &br);
                i=1;

               while(1){                
                               if(a[i]>=br) {printf("%d\n",i);break;}
                               i++ ;
                             }


                }  
return 0;
}

[laserlight]

Good to see that you used code tags, but kindly indent your code properly so that other users can read it more easily.

[iMalc]

Arrays start at zero, not one. Your for-loop is a buffer overrun bug.

[tabstop]

Is br supposed to represent a number, or a number of digits? (In other words, if I type in 10, am I supposed to get the first number with n! bigger than 10, or with n! bigger than 1000000000?) You're checking the latter, although the comments indicate the former. (And don't forget the array indexing as mentioned by iMalc.) If the former, you won't need nearly so many entries in your array a, since 13! is bigger than a 32-bit integer. If the latter, then, that may be as good as it gets unless you want to realloc when they enter a number, as opposed to guessing the largest number they're going to type.

[laserlight]

That reminds me...

should i use some other data structure than dynamic array

If your aim is to find the smallest number whose factorial is greater than or equal to the number entered by the user, then you do not need to use an array or other container unless you want to implement an arbitrary precision maths library or something. A simple loop will do, assuming that the values are within the range of the data type.

[tabstop]

That reminds me...


If your aim is to find the smallest number whose factorial is greater than or equal to the number entered by the user, then you do not need to use an array or other container unless you want to implement an arbitrary precision maths library or something. A simple loop will do, assuming that the values are within the range of the data type.

I think the array is there so that we don't have to recalculate values, since we're doing this an arbitrary number of times.

[Cactus_Hugger]

There shouldn't be a need to recalculate.
As I understand it, the problem is x! >= u, where u is user entered number, and we want the smallest possible x. A very simple solution would be to start with 1!, then 2!, 3!, etc. But you don't have to recalculate each factorial when proceeding along like that - what I think laserlight was hinting at - since if you already know 2! = 2, then 3! = 2! * 3. Just keep basing each new factorial off the last one, until you exceed that user entered number (u).

[tabstop]

There shouldn't be a need to recalculate.
As I understand it, the problem is x! >= u, where u is user entered number, and we want the smallest possible x. A very simple solution would be to start with 1!, then 2!, 3!, etc. But you don't have to recalculate each factorial when proceeding along like that - what I think laserlight was hinting at - since if you already know 2! = 2, then 3! = 2! * 3. Just keep basing each new factorial off the last one, until you exceed that user entered number (u).

Well, it's not necessary, certainly. But if you just ran the loop to 10000, and now need to run it to 20000, wouldn't it be nice if you could start at 10000 instead of from scratch? Presumably the original intent at one time was to resize the array when a larger number was entered, although it doesn't seem to have ended up that way. (Since right now it is essentially a static array.)

Edit to add: And of course if they enter 9000 the second time, you don't have to do any calculating at all, since you stored the answers.

[kernelio]

Well, it's not necessary, certainly. But if you just ran the loop to 10000, and now need to run it to 20000, wouldn't it be nice if you could start at 10000 instead of from scratch? Presumably the original intent at one time was to resize the array when a larger number was entered, although it doesn't seem to have ended up that way. (Since right now it is essentially a static array.)

Edit to add: And of course if they enter 9000 the second time, you don't have to do any calculating at all, since you stored the answers.

Yes you totally get my idea and what i'm doing bit is there any way to optimize the solution

BTW the number of test cases is 1000
and you can get more informations about the digits of a factorial from
http://en.wikipedia.org/wiki/Factorial

[tabstop]

I can't see anything you can do inside the loop -- the question is how big should you make your array. This size comes down to whether your comments or your code is correct, since they don't match, but maybe you don't need to go to 1000000?

[laserlight]

I think you need to be clear on what you are trying to solve. You talk about the digits of a factorial, yet you say your program "needs to find the first smallest number who's factorial is bigger or equal to the inputed number". I do not think determining the number of digits of a factorial in a given base can accurately determine which is the smallest number whose factorial is greater than or equal to a given number.

[kernelio]

I think you need to be clear on what you are trying to solve. You talk about the digits of a factorial, yet you say your program "needs to find the first smallest number who's factorial is bigger or equal to the inputed number". I do not think determining the number of digits of a factorial in a given base can accurately determine which is the smallest number whose factorial is greater than or equal to a given number.

Tt's a bit of tricky bit
"needs to find the first smallest number who's(number of a factorial's DIGITS) is bigger or equal to the inputed number