CODEWITHSUNDEEP
c
huangli
huangli

Reputation: 454

why is my 3n+1 problem solution wrong

I have recently started reading "Programming Challenges" book by S. Skiena and believe or not I am kind of stuck in the very first problem.

Here's a link to the problem: 3n+1 problem

Here's my code:

 #include <stdio.h>

long get_cycle(long input){
    if (input == 1){
        return 1;
    }
    else{
        if (input & 1){
            return 2 + get_cycle((3*input+1)>>1);
        }
        else{
            return 1 + get_cycle(input >> 1);
        }
    }
}

long get_range_cycle(int k, int j){
    int i;
    int max = 0;
    int current_cycle;
    int to = k > j ? k : j;
    int from = k < j ? k : j;
    for (i=from; i<=to; ++i){
        current_cycle = get_cycle(i);
        if (current_cycle > max){
            max = current_cycle;
        }
    }
    return max;
}

int main(){
    long p, q;
    long re[100][3];
    int i = 0;
    while (scanf("%ld %ld",&p,&q) == 2){
        re[i][0] = p;
        re[i][1] = q;
        re[i][2] = get_range_cycle(p,q);
        ++i;
    }
    int j;
    for (j=0; j<i; ++j){
        printf("%ld %ld %ld\n",re[j][0],re[j][1],re[j][2]);
    }
}

what is wrong with my code? the input and out is exactly the same with sample.But the submission result is always run time error!

Upvotes: 0

Views: 848

Answers (2)

Arne Bergene Fossaa
Arne Bergene Fossaa

Reputation: 652

I believe that the problem you seek answer for is in the answer @Elemental . If you fix that, however, your solution will time out.

What you should do is to build up a list of all answers between 0 and 1000000. This can be done in linear time (I will not give you the full answer).

Upvotes: 0

Elemental
Elemental

Reputation: 7521

You're code seems to assume maximum 100 lines in the input file - the sample data they are testing on might be bigger? They make no explicit claim wrt the maximum set size of the input data.

Upvotes: 1

Related Questions