CODEWITHSUNDEEP
algorithminteger-overflow
breach10ck
breach10ck

Reputation: 168

Google Code Jam 2008 Round 1A Q 3

For the problem statement in google codejam 2008: Round 1A Question 3

In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)n.

For example, when n = 5, (3 + √5)5 = 3935.73982... The answer is 935.

For n = 2, (3 + √5)2 = 27.4164079... The answer is 027.

My solution based on the idea that T(i) = 6*T(i-1) - 4*T(n-2) + 1, where T(i) is the integer part for n=i is as below:

#include<stdio.h>
int a[5000];
main(){
    unsigned long l,n;
    int i,t;
    a[0]=1;
    a[1]=5;
    freopen("C-small-practice.in","r",stdin);
    scanf("%d",&t);
    for(i=2;i<5000;i++)
            a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000;
    i=t;
    for(i=1;i<=t;i++){

            scanf("%ld",&n);
            printf("Case #%d: %.3d\n",i,a[(int)n]);
    }
    fclose(stdin);
}

in the line a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000; i know there will be integer overflow, but i dont know why by adding 10,000 i am getting the right answer. I am using GCC compiler where sizeof(int)=4

Can anyone explain what is happening ?

Upvotes: 1

Views: 543

Answers (1)

Dennis Meng
Dennis Meng

Reputation: 5187

First off, the line

a[i]=(6*a[i-1]-4*a[i-2]+10001)%1000;

shouldn't actually cause any overflow, since you're keeping all previous values below 1000.

Second, did you consider what happens if 6*a[i-1]-4*a[i-2]+1 is negative? The modulus operator doesn't have to always return a positive value; it can also return negative values as well (if the thing you are dividing is itself negative).

By adding 10000, you've ensured that no matter what the previous values were, the value of that expression is positive, and hence the mod will give a positive integer result.

Expanding on that second point, here's 6.5.5.6 of the C99 specification:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

A note beside the word "discarded" states that / "truncates toward zero". Hence, for the second sentence to be true, the result of a % b when a is negative must itself be negative.

Upvotes: 2

Related Questions