CODEWITHSUNDEEP
c
Number945
Number945

Reputation: 4940

SPOJ ROOTCIPH wrong answer

Here is the SPOJ problem ROOTCIPH.

I have solved it by two ways in C. One approach gives the correct answer and the other is wrong.

We won’t discuss the how to solve the problem. The solution is simple. It is always aa -2b. (Think in term of roots of a cubic equation...) Anyway, the question does not relate to it. This detail I gave so that one can run their solution to the source and analyse more.

Now the question:

In the code below, if instead of 'int', I take long long, my answer is shown correct, otherwise for 'int' it is shown wrong. I have taken %lld in printf, so even if the integer bound exceeds, it should handle.

Wrong code:

int main()
{
    int a, b, c;
    int t;

    scanf("%d", &t);

    while(t--)
    {
        scanf("%d%d%d", &a, &b, &c);
        printf("%lld\n", 1LL*a*a - 2*1LL*b);
    }

    return 0;
}

Right code:

int main()
{
    long long a, b, c;
    int t;

    scanf("%d", &t);

    while(t--)
    {
        scanf("%lld%lld%lld", &a, &b, &c);
        printf("%lld\n", a*a - 2*b);
    }

    return 0;
}

Note that absolute value of a, b, and c will not exceed 10^8.

Why does the first approach give the wrong solution? You can run the solution in the link given and check.

According to C operator precedence table , * have left to right associativity.

Upvotes: 0

Views: 266

Answers (2)

Antoine C.
Antoine C.

Reputation: 3952

If your answer is not in the interval [-2 147 483 648 ; 2 147 483 647], then it can't fit into an int, which is stored in 32 bits (or 16 if you are on a 16 bits system, so in [-32 768 ; 32 767]).

A long long integer is stored in 64 bits, regardless of your system.

Upvotes: 0

Scott Hunter
Scott Hunter

Reputation: 49813

As Engineer2021 suggests, using long long's, which can hold bigger numbers than int's, is likely the difference. For example, part of your expression is a*a; even if you multiply that by a 1LL, in effect converting it, the damage may have already been done.

Upvotes: 1

Related Questions