4
\$\begingroup\$

I built a program in C that can tell how many odd and even Fibonacci numbers there are between a given range.

Input Specification

First line of the input contains T, representing the number of test cases (1 ≤ T ≤ 50). Each test case contains two integers N and M (1 ≤ N ≤ M ≤ 1018) and (|N-M| ≤ 105), where N is the Nth Fibonacci number and M is the Mth Fibonacci number of the sequence.

Output Specification

Case T:
Odd = total number of odd Fibonacchi numbers between N and M
Even = total number of even Fibonacchi numbers between N and M

The full code

#include <stdio.h>
#include <math.h>

int main()
{
    int T, i, j, k;
    scanf("%d", &T);

    for (i=0; i<T; i++)
    {
        int N, M, val;
        scanf("%d%d", &N,&M);
        val = abs(N-M)+1;

        int n,m;
        if (M>N) { n=N; m=M; }
        if (N>M) { n=M; m=N; }

        int b_tri, e_tri, even=0, odd=0;
        if (n%3==1) { b_tri=3; even++; odd+=2; } 
        if (n%3==2) { b_tri=2; odd+=2; }
        if (n%3==0) { b_tri=1; odd++;  }

        if (m%3==1) { e_tri=1; even++; } 
        if (m%3==2) { e_tri=2; odd++;  even++; }
        if (m%3==0) { e_tri=3; odd+=2; even++; }

        val-=(e_tri+b_tri);
        val/=3;

        for (j=0; j<val; j++)
        {
            even++;
            odd+=2;
        }

        printf("Case %d:\nOdd = %d\nEven = %d\n", i+1, odd, even);
    }

    return 0;
}

Logic

  • 1st Fibonacci number is 0 (even).
    2nd Fibonacci number is 1 (odd).
    3rd Fibonacci number is 1 (even + odd = odd).

  • 4th Fibonacci number is 2 (odd + odd = even).
    5th Fibonacci number is 3 (odd + even = odd).
    6th Fibonacci number is 5 (even + odd = odd).

  • 7th Fibonacci number is 8 (even).
    8th Fibonacci number is 13 (odd).
    9th Fibonacci number is 21 (odd).


I'd like advice on:

  • Using mathematical formulas instead of loops to calculate this
  • Making the code more efficient
\$\endgroup\$
  • 2
    \$\begingroup\$ Given two Fibonacci numbers N and M (N < M), you aim to compute (1) the number of all odd/even integers between N and M (including N and M), or (2) the number of all odd/even Fibonacci numbers (including N and M); please specify. \$\endgroup\$ – coderodde Aug 7 '17 at 15:35
  • \$\begingroup\$ @coderodde Question edited. \$\endgroup\$ – Soha Farhin Pine Aug 8 '17 at 4:42
  • \$\begingroup\$ Please also link the challenge as the current explanation is ambiguous as @coderodde has stated. I lean towards the number of odd/even Fibonacci numbers which is (2) in the comment as the number of odd and even integers is trivial and uncharacteristic of a programming challenge question. Also the question says to list all numbers that are even or odd but you're listing the number of numbers that are even or odd. \$\endgroup\$ – Emily L. Aug 8 '17 at 12:05
  • \$\begingroup\$ @EmilyL. Read the question again carefully --- "I built a program in C that can tell how many odd and even Fibonacci numbers there are between a given range." \$\endgroup\$ – Soha Farhin Pine Aug 8 '17 at 13:54
  • \$\begingroup\$ I read the output specification, I do not assume that what you have implemented and what you should have implemented are the same thing. \$\endgroup\$ – Emily L. Aug 8 '17 at 14:21
5
\$\begingroup\$

I'm going to assume you tested it for several inputs and got the right values. Your logic seems right so if a couple test cases work, it probably works. But I didn't look carefully for any off-by-one like errors.

There is one logic issue that I see:

You don't set n and m if N = M. Double check your two if statements in the beginning of the loop; you only check for strict inequality on both sides. One of them should change to a >= or <=, or better yet just use if-else instead of two ifs.

As for optimization...

In terms of an average computer, your program is good enough for any N and M because you specify N,M < 1018. Even if you don't, for-loops by themselves are pretty cheap.

However, there are still optimizations/cleanups.

The biggest one is your last for loop:

for (j=0; j<val; j++)
{
    even++;
    odd+=2;
}

This can just be:

even+=val;
odd+=2*val

Your two if chains can turn into if, else if, else instead of three ifs (same thing for your first if pair, which should just be if else)

if (...) { }
else if (...) { }
else (...) { }

although the compiler will most likely optimize that for you.

I think that's the best you can do for your current algorithm.

However, it seems odd to me that you are checking for all mod cases for n and m; I think your idea is that you know the pattern for the large chunks in between N and M but you want to trim off the edge cases. Now, you won't need to trim down the case when n%3==1 or m%3==0, because you can just treat that as the even++, odd+=2 chunk.

n=m case

In programming you can always cop out :)

Here is how I would address the n=m case even though it's not too beautiful:

if (N == M)
{
  printf("Odd: 0, Even: 0"); //format this to match your output
  break;  // break ends the current for loop iteration in this context
}
else if (N > M)
{
  n = M; m = N;
}
else
{
  n = N; m = M;
}
\$\endgroup\$
  • \$\begingroup\$ Thank you very much! +1! Wonderful answer! yeah, the program does work. But I do need to trim down the case when it's n%3==0, I can avoid it when n%3==1. \$\endgroup\$ – Soha Farhin Pine Aug 8 '17 at 4:26
  • \$\begingroup\$ I can't think of a way to make the code work even when n = m, without making the code very large and inefficient. \$\endgroup\$ – Soha Farhin Pine Aug 8 '17 at 4:49
  • \$\begingroup\$ It's actually 10^18, not 1018. \$\endgroup\$ – Soha Farhin Pine Aug 8 '17 at 5:44
  • \$\begingroup\$ Ok in that case you need to fix your int. You probably want to use 64 bit ints (int tends to be 32 bit int on most computers). 32 bit int goes up to 2 billion, ~ 10^9. 64 bit int will go to orders of 10^18. And regarding the n=m case, I don't know how to format code in comments so I'll edit this answer and put it in the bottom \$\endgroup\$ – C. Sano Aug 8 '17 at 16:55
0
\$\begingroup\$

Updated code as per C. Sano's suggestions:

#include <stdio.h>
#include <math.h>

int main()
{
    int T, i, j, k;
    scanf("%d", &T);

    for (i=0; i<T; i++)
    {
        long long N, M;
        scanf("%lld%lld", &N,&M);
        long long val, even=0, odd=0;
        val = abs(N-M)+1;

        if (val==1)
        {
            if (N%3==1) { even++;  }
            else { odd++; }
        }

        else 
        {
            long long n,m;
            if (M>N) { n=N; m=M; }
            if (N>M) { n=M; m=N; }

            int b_tri=0, e_tri=0;
            if (n%3==2) { b_tri+=2; odd+=2; }
            if (n%3==0) { b_tri+=1; odd++;  }
            //--------------------------------
            if (m%3==1) { e_tri+=1; even++; } 
            if (m%3==2) { e_tri+=2; odd++;  even++; }

            val-=(e_tri+b_tri);
            val/=3;

            even+=val;
            odd+=(2*val);
        }

        printf("Case %lld:\nOdd = %lld\nEven = %lld\n", i+1, odd, even);
    }

    return 0;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.