1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Help !!!

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

  1. ministerot

    ministerot New Member

    Joined:
    Jan 19, 2008
    Messages:
    2
    Likes Received:
    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. Salem

    Salem New Member

    Joined:
    Nov 15, 2007
    Messages:
    133
    Likes Received:
    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. ministerot

    ministerot New Member

    Joined:
    Jan 19, 2008
    Messages:
    2
    Likes Received:
    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. Salem

    Salem New Member

    Joined:
    Nov 15, 2007
    Messages:
    133
    Likes Received:
    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.
    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
     
  5. oogabooga

    oogabooga New Member

    Joined:
    Jan 9, 2008
    Messages:
    115
    Likes Received:
    11
    Trophy Points:
    0
    A couple of questions:
    1. Does your program run?
    2. How long does it take to run?
    3. Does it get the correct results?
    4. Why are you storing the "number of digits" of factorials?
    5. Where does the number 205019 come from?
     

Share This Page