CODEWITHSUNDEEP
c
Mehedi H.
Mehedi H.

Reputation: 157

UVA's 3n+1 wrong answer although the test cases are correct . . .?

UVA problem 100 - The 3n + 1 problem

I have tried all the test cases and no problems are found. The test cases I checked:

But why I get wrong answer all the time?

here is my code:

#include "stdio.h"

unsigned long int cycle = 0, final = 0;

unsigned long int calculate(unsigned long int n)
{
    if (n == 1)
    {
        return cycle + 1;
    }
    else
    {
        if (n % 2 == 0)
        {
            n = n / 2;
            cycle = cycle + 1;
            calculate(n);
        }
        else
        {
            n = 3 * n;
            n = n + 1;
            cycle = cycle+1;
            calculate(n);
        }
    }
}


int main()
{
    unsigned long int i = 0, j = 0, loop = 0;
    while(scanf("%ld %ld", &i, &j) != EOF)
    {
        if (i > j)
        {
            unsigned long int t = i;
            i = j;
            j = t;
        }
        for (loop = i; loop <= j; loop++)
        {
            cycle = 0;
            cycle = calculate(loop);

            if(cycle > final)
            {
                final = cycle;
            }
        }
        printf("%ld %ld %ld\n", i, j, final);
        final = 0;
    }
    return 0;
}

Upvotes: 1

Views: 3174

Answers (5)

Kaz
Kaz

Reputation: 58617

Part 1

This is the hailstone sequence, right? You're trying to determine the length of the hailstone sequence starting from a given N. You know, you really should take out that ugly global variable. It's trivial to calculate it recursively:

long int hailstone_sequence_length(long int n)
{
  if (n == 1) {
    return 1;
  } else if (n % 2 == 0) {
    return hailstone_sequence_length(n / 2) + 1;
  } else {
    return hailstone_sequence_length(3*n + 1) + 1;
  }
}

Notice how the cycle variable is gone. It is unnecessary, because each call just has to add 1 to the value computed by the recursive call. The recursion bottoms out at 1, and so we count that as 1. All other recursive steps add 1 to that, and so at the end we are left with the sequence length.

Careful: this approach requires a stack depth proportional to the input n.

I dropped the use of unsigned because it's an inappropriate type for doing most math. When you subtract 1 from (unsigned long) 0, you get a large positive number that is one less than a power of two. This is not a sane behavior in most situations (but exactly the right one in a few).

Now let's discuss where you went wrong. Your original code attempts to measure the hailstone sequence length by modifying a global counter called cycle. However, the main function expects calculate to return a value: you have cycle = calculate(...).

The problem is that two of your cases do not return anything! It is undefined behavior to extract a return value from a function that didn't return anything.

The (n == 1) case does return something but it also has a bug: it fails to increment cycle; it just returns cycle + 1, leaving cycle with the original value.

Part 2

Looking at the main. Let's reformat it a little bit.

int main()
{
  unsigned long int i=0,j=0,loop=0;

Change these to long. By the way %ld in scanf expects long anyway, not unsigned long.

  while (scanf("%ld %ld",&i,&j) != EOF)

Be careful with scanf: it has more return values than just EOF. Scanf will return EOF if it is not able to make a conversion. If it is able to scan one number, but not the second one, it will return 1. Basically a better test here is != 2. If scanf does not return two, something went wrong with the input. 

  {
    if(i > j)
    {
      unsigned long int t=i;i=j;j=t;
    }
    for(loop=i;loop<=j;loop++)
    {
      cycle=0;
      cycle=calculate(loop );

      if(cycle>final)
      { 
        final=cycle;
      } 
    }

calculate is called hailstone_sequence_length now, and so this block can just have a local variable: { long len = hailstone_sequence_length(loop); if (len > final) final = len; }

Maybe final should be called max_length?

    printf("%ld %ld %ld\n",i,j,final);
    final=0;

final should be a local variable in this loop since it is separately used for each test case. Then you don't have to remember to set it to 0.

  }
  return 0;
}

Upvotes: 0

Walter R
Walter R

Reputation: 543

The clue is that you receive i, j but it does not say that i < j for all the cases, check for that condition in your code and remember to always print in order:

<i>[space]<j>[space]<count>

Upvotes: 5

pmg
pmg

Reputation: 108978

If the input is "out of order" you swap the numbers even in the output, when it is clearly stated you should keep the input order.

Upvotes: 2

Keith Nicholas
Keith Nicholas

Reputation: 44308

Here's a one liner just for reference 

int three_n_plus_1(int n)
{
    return n == 1 ? 1 : three_n_plus_1((n % 2 == 0) ? (n/2) : (3*n+1))+1;
}

Not quite sure how your code would work as you toast "cycle" right after calculating it because 'calculate' doesn't have explicit return values for many of its cases ( you should of had compiler warnings to that effect). if you didn't do cycle= of the cycle=calculate( then it might work?

and tying it all together :-

int three_n_plus_1(int n)
{
    return n == 1 ? 1 : three_n_plus_1((n % 2 == 0) ? (n/2) : (3*n+1))+1;
}

int max_int(int a, int b) { return (a > b) ? a : b; }
int min_int(int a, int b) { return (a < b) ? a : b; }

int main(int argc, char* argv[])
{   
    int i,j;
    while(scanf("%d %d",&i, &j) == 2)
    {
        int value, largest_cycle = 0, last = max_int(i,j);
        for(value = min_int(i,j); value <= last; value++) largest_cycle = max_int(largest_cycle, three_n_plus_1(value));
        printf("%d %d %d\r\n",i, j, largest_cycle);
    }   
}

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49893

Don't see how you're test cases actually ever worked; your recursive cases never return anything.

Upvotes: 1

Related Questions