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; }
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?
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.
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. http://faq.cprogramming.com/cgi-bin/smartfaq.cgi?answer=1047673478&id=1043284351 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
A couple of questions: Does your program run? How long does it take to run? Does it get the correct results? Why are you storing the "number of digits" of factorials? Where does the number 205019 come from?