# Help !!!

Discussion in 'C' started by ministerot, Jan 19, 2008.

1. ### ministerotNew Member

Joined:
Jan 19, 2008
Messages:
2
0
Trophy Points:
0
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
ex.
input
3
1
101
2008
output
1
70
811

should i use some other data structure(tree or something) than dynamic array??

Code:
```[COLOR=Green]#include <math.h>
#include <stdio.h>
#include <stdlib.h> [/COLOR]

int main()
{
int i=0,br,t=0,br_cif;
int *a= (int*)malloc(sizeof(int)*205019);
scanf("%d",&t);

float dig=0.0;           [COLOR=Red]//for log10[/COLOR]
for (i = 1; i <=205019; i++)
{
dig +=log10(i);
a[i]=(int)floor(dig)+1;      //[COLOR=Red]aproximation[/COLOR]
}

while(t--){
scanf("%d", &br);
i=1;
//[COLOR=Red]we search for the first number[/COLOR]
while(1){
if(a[i]>=br) {printf("%d\n",i);break;}
i++ ;
}

}
return 0;
}
```

2. ### SalemNew Member

Joined:
Nov 15, 2007
Messages:
133
5
Trophy Points:
0
Occupation:
Please don't PM me for 1:1 support.
Well the number of factorials you can store in a 32-bit int is pretty small. Perhaps a lookup table and a search would be better?

3. ### ministerotNew Member

Joined:
Jan 19, 2008
Messages:
2
0
Trophy Points:
0
YES but I dont store the numbers of a factorials,
but the number of the digits of the factorial.

I don't know how to search the array any faster beacuse i need THE SMALLESET INTEGER WOES FACTORIAL IS GREATHER THAN OR EQUAL TO THE INPUTET NUMBER.

4. ### SalemNew Member

Joined:
Nov 15, 2007
Messages:
133
5
Trophy Points:
0
Occupation:
Please don't PM me for 1:1 support.
Since your array is sorted, I guess you could use the bsearch() function in stdlib.h to search the array a lot quicker than a linear search would do.

> for (i = 1; i <=205019; i++)
Arrays start at 0, not 1
They also end at 1 step before the array length, so use <, not <=

> int *a= (int*)malloc(sizeof(int)*205019);
If this really is a C program, then the cast is unnecessary.
If you remove the cast, and get something about casting void*, then you're compiling your C program with a C++ compiler. Adjust your tools to do the right thing, not maul the code to make it fit.

There's no need to shout.
http://www.catb.org/~esr/faqs/smart-questions.html#writewell

Joined:
Jan 9, 2008
Messages:
115