what is wrong with my 3n+1 solution?

Question

I get wrong answer from both online judges.

#include <stdio.h>

int main(int argc, char * argv[])
{
 long long i=0;
 long long j=0;
 long long p=0;
 long long q=0;
 long long larger;
 long long smaller;
 long long cycle_length=1;
 long long max_cycle_length=1;

 while (scanf("%lld %lld",&p,&q) !=EOF)
 {
  /*check validity of input*/
  if (p <= 0 || p >= 1000000 || q <= 0 || q >= 1000000) continue;
  max_cycle_length=1;
  if (p > q)
  {
   larger = p;
   smaller = q;
  }
  else
  {
   larger = q;
   smaller = p;
  }
  for (i=smaller;i<=larger;i++)
  {
   cycle_length = 1;
   /*printf("i = %lld\r\n",i);*/
   j = i;
   while (j > 1)
   {
   /*printf("j = %lld\r\n",j);*/
    if ((j % 2) == 0)
    {
     j = j / 2;
    }
    else
    {
     j = 3*j + 1;
    }
    cycle_length++;
   }
   if (cycle_length > max_cycle_length)
    max_cycle_length = cycle_length;
   /*printf("cycle_length = %lld\r\n", cycle_length);*/
  }
  printf("%lld %lld %lld \r\n",p,q,max_cycle_length);
 }
 return 0;
}

Answer 1

Did you verify your code using the sample input and sample output:

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174

?

The only minor problems I see are:

while (scanf("%lld %lld",&p,&q) !=EOF)

should probably be:

while (scanf("%lld %lld", &p, &q) == 2)

and:

printf("%lld %lld %lld \r\n",p,q,max_cycle_length);

should probably be:

printf("%lld %lld %lld\n", p, q, max_cycle_length);

Answer 2

Do the online judges accept C99?

long long (and their printf conversion specification) is a C99 type. It wasn't defined by the C89 standard.

Answer 3

stdout is opened in text mode by the library even before main starts. That means that the library is responsible for managing the differences in line breaks between your program and the Operating System.

Drop the \r (and extra spaces) from your printf() calls

printf("%lld %lld %lld\n", p, q, max_cycle_length);