You are not logged in. Please login at www.codechef.com to post your questions!

×

FCTRL2: Doubt in execution time

#include <stdio.h>
#include <malloc.h>

void mult(int ,int* ,int );

int main()
{
 int a,i,b[200],k,l,d,c,x,temp;
 int *m;
 scanf("%d",&a);
 m = (int*) malloc (a*sizeof(int));
 for(i=0;i<a;i++)
 {
  scanf("%d",m+i);
 }
 for(i=0;i<a;i++)
 {
  k=0;
  l=*(m+i);
  while(l/10!=0)
  {
   b[k]= l%10;
   l=l/10;
   k++;
  }
  b[k] = l;
  for(d=*(m+i)-1;d>=1;d--)
  {
   temp=0;
   for(c=0;c<=k;c++)
   {
    x=b[c]*d+temp;
    b[c] = x%10;
    temp = x/10;
   }
   while(temp!=0)
   {
    b[++k]=temp%10;
    temp = temp/10;
   }
  }
  for(c=k;c>=0;c--)
  {
   printf("%d",b[c]);
  }
  printf("\n",k);
 }
 return 0;
}

==============================================================================

#include <stdio.h>
#include <malloc.h>

void mult(int ,int* ,int );

int main()
{
 int a,i,b[200],k,l;
 int *m;
 scanf("%d",&a);
 m = (int*) malloc (a*sizeof(int));
 for(i=0;i<a;i++)
 {
  scanf("%d",m+i);
 }
 for(i=0;i<a;i++)
 {
  k=0;
  l=*(m+i);
  while(l/10!=0)
  {
   b[k]= l%10;
   l=l/10;
   k++;
  }
  b[k] = l;
  mult(*(m+i)-1,b,k);
 }
 return 0;
}

void mult(int i,int b[],int k)
{
 int c,temp=0,l=0,x;
 if(i!=1)
 {
  for(c=0;c<=k;c++)
  {
   x=b[c]*i+temp;
   b[c] = x%10;
   temp = x/10;
  }
  while(temp!=0)
  {
   b[++k]=temp%10;
   temp = temp/10;
  }
  mult(i-1,b,k);
 }
 else
 {
  for(c=k;c>=0;c--)
  {
   printf("%d",b[c]);
  }
  printf("\n\n");
 }
}

==============================================================================

In the above two codes the first code is executing perfectly but for the second one it is showing time limit exceeded. Why is that ? The logic I have used is same in both the cases.

asked 02 May '12, 12:13

Psyther's gravatar image

0★Psyther
1111
accept rate: 0%

edited 10 Jul '12, 13:06

admin's gravatar image

0★admin ♦♦
17.4k347487515


without running your programs, i think i'm able to see a big difference between each of them. you replaced a simple for loop (with an inner condition asserting an exit when d < 1) by a recursive function asserting an exit when i == 1. if (it may be possible or it may not be, i don't know) i becomes < 1 for any reason (starting from 0, for instance), your recursive loop never ends, or actually ends when your i variable reaches 1 in an underflow (as you declared i as a signed int). maybe you can try to change the recursive function exit condition to the same as in your first code, meaning i < 1, not i == 1. hope it helps. i'll have a look deeper if this trick doesn't solve your problem. good luck :)

link

answered 03 May '12, 02:35

cyberax's gravatar image

2★cyberax ♦
3.4k21955
accept rate: 20%

edited 03 May '12, 02:37

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,368
×214
×67

question asked: 02 May '12, 12:13

question was seen: 1,308 times

last updated: 10 Jul '12, 13:06