fibonacci - HackerRank gives 'Wrong Answer' for all hidden test cases : euler 2 / C++

Question

the question can be viewed on : https://www.hackerrank.com/contests/projecteuler/challenges/euler002/problem

when i test against my own input, i find it to be correct but hacker-rank shows all test cases as failed

my code is as follows :

#include<iostream>

using namespace std;

int retevenfib(unsigned long int &a,unsigned long int &b);

int main(){

    unsigned long int fib1 = 1,fib2 = 2,hold = 2;
    double evensum;

    cout<<"enter no of tries:";
    int t;
    cin>>t;

    cout<<"enter items sequentially: ";
    long int numarr[20];
    for(int i = 0; i < t ; i++)
        cin>>numarr[i];


    for (int j = 0; j < t; j++)
    {
        evensum = 0;
        hold = 2; fib1 = 1; fib2 = 2;
        while(fib2 < numarr[j])
        {
            evensum += hold;
            hold = retevenfib(fib1,fib2);
        }
        cout<<evensum<<endl;
    }
    return 0;
}

int retevenfib(unsigned long int &a,unsigned long int &b)
{
    for(int i = 0; i < 3; i++)
    {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

question from:https://stackoverflow.com/questions/65935535/hackerrank-gives-wrong-answer-for-all-hidden-test-cases-euler-2-c

Answer 1

The very good message is: You still have the chance to go away from all this nonesense pages. I understand that you wonder why it fails, even for numbers below 20.

You need to understand that those pages ask for exact input and exact output. So, by writing:

cout<<"enter no of tries:";
cout<<"enter items sequentially: ";

you already lost the game.

Because that is not the expected output. The output shall just show the sum.

And the input is guaranteed to be correct. So, if you expect an integer, then normally you need to check the input. Because users normal users could enter "abc" and press enter. This will never happen here. So, you will never learn to use basic IO correctly.

You need to understand that there are no human beeings checking your program. Only scripts will run and push in some input and check the output exactly.

And because you do not yet know that, you have a chance to go away from those pages.

Now to the main problem: Your array. You define an array with 20 elements. And you maybe try to read 123 values in that array. This creates an out of bound error (a catastrophy) and the result is at least undefined behaviour or, also very likely, a crash of your program.

My guess would be that, if your configure your compiler for high warning levels, then you would get a corresponding message.

You do not need an array in the first place. You can omit it and simply do the calculation for each test.

Next advise. If you really want to use C++, then do never use C-Style arrays. Always use other containers like for example std::veector or std::array. There is no reason of whatsoever to use C-Style arrays in C++.

Next problem: You need to use the correct data types. For such big numbers as 10^16, an unsigned long is not big enough. It will overflow.

So please use unsigned long long or uint64_t instead.

Basically, in your whole program there is no need for any signed value at all. You should use unsigned everywhere.

Then at last, you could use "speaking" variable names. Then your program could look like the below (without any optimzation):

#include<iostream>

// Calculate the next even Fibonacci Number
//  Take advantage of the fact, that every 3rd Fibonacci number will be even
unsigned long long getNextEvenFibonacciNumber(unsigned long long& previousPreviousFibonacciNumber, 
                                              unsigned long long& previousFibonacciNumber)
{
    // Calculate 3 times the next Fibonacci number to get an even value
    for (size_t i{}; i < 3u; ++i)
    {
        unsigned long long temp = previousPreviousFibonacciNumber + previousFibonacciNumber;
        previousPreviousFibonacciNumber = previousFibonacciNumber;
        previousFibonacciNumber = temp;
    }
    // This is now the next even Fibonacci number
    return previousFibonacciNumber;
}

int main() {

    // Here we store the number of test cases
    size_t numberOfTestCases{};
    // Get number of test cases from script
    std::cin >> numberOfTestCases;

    // For all test cases . . .
    while (numberOfTestCases--) {

        // OK, up to what number shall we perform the check
        unsigned long long largestFibonacciNumberToCheck{};
        std::cin >> largestFibonacciNumberToCheck;

        // Some temporaries for our calculation
        unsigned long long previousPreviousFibonacciNumber = 1ull;
        unsigned long long previousFibonacciNumber = 2ull;
        unsigned long long  currentFibonacciNumber = 2ull;
        unsigned long long sumOfEvenFibonacciNumbers{};

        // Now, get all even Fibonacci numbers and summ them up
        while (previousFibonacciNumber < largestFibonacciNumberToCheck)
        {
            sumOfEvenFibonacciNumbers += currentFibonacciNumber;
            currentFibonacciNumber = getNextEvenFibonacciNumber(previousPreviousFibonacciNumber, previousFibonacciNumber);
        }
        // Show result
        std::cout << sumOfEvenFibonacciNumbers << '
';
    }
    return 0;
}

Comments will add quality to the code.

Your subfunction should be optimized.

And, if you wanted to win the contest, then you could precalulate all (below 30) Even-Fibonacci-Number-Sums and put them, togehter with an input range, in a compile time constexpr std::array, and just look up the value . . .

See the below example. Short, fast, easy

#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>

struct SumOfEvenFib {
    unsigned long long fibNum;
    unsigned long long sum;
    friend bool operator < (const unsigned long long& v, const SumOfEvenFib& f) { return v < f.fibNum;  }
};
constexpr std::array<SumOfEvenFib, 27u> SOEF   {{{2, 2}, { 8, 10 }, { 34, 44 }, { 144, 188 }, { 610, 798 }, { 2584, 3382 }, { 10946, 14328 }, { 46368, 60696 }, { 196418, 257114 }, { 832040, 1089154 }, 
{ 3524578, 4613732 },{ 14930352, 19544084 }, { 63245986, 82790070 }, { 267914296, 350704366 },{ 1134903170, 1485607536 }, { 4807526976, 6293134512 }, { 20365011074, 26658145586 } ,
{ 86267571272, 112925716858 }, { 365435296162, 478361013020 }, { 1548008755920, 2026369768940 }, { 6557470319842, 8583840088782 }, { 27777890035288, 36361730124070 },
{ 117669030460994, 154030760585064 }, { 498454011879264, 652484772464328 }, { 2111485077978050, 2763969850442378 }, { 8944394323791464, 11708364174233842 }, { 37889062373143906, 49597426547377748 } } };

int main() {

    // Here we store the number of test cases
    size_t numberOfTestCases{};
    // Get number of test cases from script
    std::cin >> numberOfTestCases;

    // For all test cases . . .
    while (numberOfTestCases--) {

        // OK, up to what number shall we perform the summing up
        unsigned long long largestFibonacciNumberToCheck{};
        std::cin >> largestFibonacciNumberToCheck;

        // Show sum
        std::cout << std::prev(std::upper_bound(SOEF.begin(), SOEF.end(), largestFibonacciNumberToCheck))->sum << '
';
    }
    return 0;
}

---

And for Hardcore C++ programmers, we generate the array automatically

---

#include <iostream>
#include <array>
#include <algorithm>
#include <iterator>


// ----------------------------------------------------------------------
// All the following wioll be done during compile time
// Constexpr function to calculate the nth even Fibonacci number
constexpr unsigned long long getEvenFibonacciNumber(size_t index) {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 2 };

    // calculating Fibonacci value 
    while (--index) {
        // get next even value of Fibonacci sequence 
        unsigned long long f3 = 4 * f2 + f1;

        // Move to next even number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

// Get nth even sum of Fibonacci numbers
constexpr unsigned long long getSumForEvenFibonacci(size_t index) {
    // Initialize first two even prime numbers 
    // and their sum 
    unsigned long long f1{0}, f2{2}, sum{2};

    // calculating sum of even Fibonacci value 
    while (--index) {
        // get next even value of Fibonacci sequence 
        unsigned long long f3 = 4 * f2 + f1;

        // Move to next even number and update sum 
        f1 = f2;
        f2 = f3;
        sum += f2;
    }
    return sum;
}

// Here we will store ven Fibonacci numbers and their respective sums
struct SumOfEvenFib {
    unsigned long long fibNum;
    unsigned long long sum;
    friend bool operator < (const unsigned long long& v, const SumOfEvenFib& f) { return v < f.fibNum; }
};

// We will automatically build an array of even numbers and sums during compile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<SumOfEvenFib, sizeof...(ManyIndices)>{ { {getEvenFibonacciNumber(ManyIndices + 1), getSumForEvenFibonacci(ManyIndices + 1)}...}};
};

// You may check with Binets formula
constexpr size_t MaxIndexFor64BitValue = 30u;

// Generate the required number of items
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue >());
}

// This is an constexpr array of even Fibonacci numbers and its sums
constexpr auto SOEF = generateArray();
// ----------------------------------------------------------------------


int main() {

    // Here we store the number of test cases
    size_t numberOfTestCases{};
    // Get number of test cases from script
    std::cin >> numberOfTestCases;

    // For all test cases . . .
    while (numberOfTestCases--) {

        // OK, up to what number shall we perform the summing up
        unsigned long long largestFibonacciNumberToCheck{};
        std::cin >> largestFibonacciNumberToCheck;

        // Show sum
        std::cout << std::prev(std::upper_bound(SOEF.begin(), SOEF.end(), largestFibonacciNumberToCheck))->sum << '
';
    }
    return 0;
}

Tested with MSVC 19, Clang 11 and gcc 10

Compiled with C++17