CODEWITHSUNDEEP
c++variablesglobal-variablesfibonacci
vinayawsm
vinayawsm

Reputation: 865

On declaring variables as global gives different answers

I have two similar codes

Code1:

#include <bits/stdc++.h>

using namespace std;

long long int MOD = 1000000007;

long long int fib(long long int n)
{
    if(n <= 2)
        return 1;
    long long int k = n/2;
    long long int a = fib(k+1);
    long long int b = fib(k);
    if(n%2 == 1)
        return (a*a + b*b)%MOD;
    else
    {
        long long c = 2*a - b;
        if(c < 0)
            c+=MOD;
        return (b*(c))%MOD;
    }
}

int main()
{
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

Here I define variables k,a,b as local variables. For n = 100000000, output is 908460138.

Code2:

#include <bits/stdc++.h>

using namespace std;

long long int MOD = 1000000007;

long long int a,b,c,d,k;

long long int fib(long long int n)
{
    if(n <= 2)
        return 1;
    k = n/2;
    a = fib(k+1);
    b = fib(k);
    if(n%2 == 1)
        return (a*a + b*b)%MOD;
    else
    {
        c = 2*a - b;
        if(c < 0)
            c+=MOD;
        return (b*(c))%MOD;
    }
}

int main()
{
    long long int n;
    scanf("%lld",&n);
    printf("%lld\n", fib(n));
    return 0;
}

Here I define variables k,a,b as global variables. For n = 100000000, output is 265038576.

Can anyone explain why do I get this difference in output. Code1 is giving correct output(but has a greater run time). How to resolve this?

Upvotes: 0

Views: 47

Answers (1)

Jarod42
Jarod42

Reputation: 217275

When using local variables, you have 'several' local variables a,b,c,d,k (one independent by scope).

When using global variables, you share the variable with the different call to fib:

so

a = fib(k+1);
b = fib(k);

The second call will modify previous k, a (if k > 2) and so have side effect for the current call.

Upvotes: 3

Related Questions