HackerRank gives 'Wrong Answer' for all hidden test cases

Question

I was trying Project Euler Challenge #2 on the HackerRank, and my Python code passed the sample test case but failed the hidden test cases, with the compiler displaying 'Wrong Answer' for all of them. Here is the link to the challenge- https://www.hackerrank.com/contests/projecteuler/challenges/euler002/problem

What is the mistake I have committed?

I have tried various inputs (including huge values and many test cases). It had given me correct answers when I executed them in PyCharm editor. I think I have covered all range of inputs. If not, please let me know.

t=int(input().rstrip())

n=[]

for i in range(t):
    n.append(int(input().rstrip()))

inp=sorted(n)

f1=1
f2=2
sf=2 #sum of fibonacci
it=iter(inp)
value=next(it)
out=[None]*len(n)
maxi=max(inp)

while f2<=maxi:

    f1=f1+f2
    f2=f1+f2
    f1=f2-f1
    f2=f2-f1

    if f2>value:
        out[n.index(value)]=sf

        try:
            value=next(it)
        except StopIteration:
            pass

    if f2%2==0:
        sf=sf+f2


print(*out,sep='\n')

Answer 1

I'm not sure this answer will help future readers, but let's go though your code quickly.

Let's try a different input:

3
10
11
12

For the new examples, the outputs should be 10 as well (the next number in the sequence after 8 is 13):

10
10
10

If we run your program with this input, we get:

10
None
None

Oops! That looks like a bug. Where is the None coming from? The list of outputs is filled with None when the program initializes: out=[None]*len(n) so it seems like the correct value is not put in the output list.

The line where the values are filled in: out[n.index(value)]=sf only runs once for each item in the input list. The problem seems to be that inputs that have the same output will only be computed once.

I'm guessing you were trying to reduce the runtime complexity by calculating all values in one iteration, instead of generating the Fibonacci sequence for each input. That's smart!

So, we noticed that inputs with the same output value only updates the first value in output. What if we do for all values smaller than f2 instead?

t=int(input().rstrip())

n=[]

for i in range(t):
    n.append(int(input().rstrip()))

inp=sorted(n)

f1=1
f2=2
sf=2 #sum of fibonacci
it=iter(inp)
value=next(it)
out=[None]*len(n)
maxi=max(inp)

while f2<=maxi:

    f1=f1+f2
    f2=f1+f2
    f1=f2-f1
    f2=f2-f1

    while f2>value:
        out[n.index(value)]=sf

        try:
            value=next(it)
        except StopIteration:
            break

    if f2%2==0:
        sf=sf+f2

print(*out,sep='\n')

Only two things changed, the if f2>value: is now while f2 > value: and instead of pass when there are no more values, we break out of the while loop instead. That takes care of the first problem, it seems. The output is now what we expected:

10
10
10

Ok, let's try another input. Remember, it doesn't say anywhere that the inputs are unique. They might occur more than once - what will happen if they do? Let's try this input:

2
100
100

The output should just be 44 twice, right? With the new version above, we get:

44
None

Oh no, another bug. The problem seems to be on the line that updates the output, again: out[n.index(value)]=sf. It's clear that if the input is something like [100, 100], the output should be [44, 44] but n.index(100) will always be 0. The index method will only return the first index that matches a value. Now we have more than one and this will not work.

There are obviously many solutions to this, but let's put the answers in a dictionary called results instead and create out at the end once we know what all the outputs are supposed to be:

t=int(input().rstrip())

n=[]

for i in range(t):
    n.append(int(input().rstrip()))

inp=sorted(n)

f1=1
f2=2
sf=2 #sum of fibonacci
it=iter(inp)
value=next(it)
results = {}
maxi=max(inp)

while f2<=maxi:

    f1=f1+f2
    f2=f1+f2
    f1=f2-f1
    f2=f2-f1

    while f2>value:
        results[value] = sf

        try:
            value=next(it)
        except StopIteration:
            break

    if f2%2==0:
        sf=sf+f2

out = [results[x] for x in n]
print(*out, sep='\n')

This one passes all the HackerRank test cases as well.

You were so close, nice!

Answer 2

The problem in your print(*out,sep='\n'). You should call print in loop

Try this. All tests passed

#!/bin/python3

import sys


t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())

    if (n < 2) : 
        print(0)
        continue
    # Initialize first two even prime numbers and their sum 
    ef1, ef2 = 0, 2
    sm = ef1 + ef2 

    # calculating sum of even Fibonacci value 
    while ef2 <= n: 
        # get next even value of Fibonacci sequence
        ef3 = 4 * ef2 + ef1 

        # If we go beyond limit, we break loop 
        if ef3 > n: 
            break

        # Move to next even number and update sum
        ef1, ef2 = ef2, ef3
        sm = sm + ef2 

    print(sm)