C++

Forum

 
 
Getting wrong output

Gamemaster007 (26)
So the question is https://www.hackerrank.com/challenges/is-fibo


Here is my code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 

#include <iostream>
#include <math.h>
using namespace std;
 

bool isPerfectSquare(unsigned long long x)
{
    unsigned long long s = sqrt(x);
    return (s*s == x);
}
 

bool isFibonacci(unsigned long long n)
{
    
    return isPerfectSquare(5*n*n + 4) ||
           isPerfectSquare(5*n*n - 4);
}
 

int main()
{
	unsigned long long T;
	unsigned long long N;
	cin>>T;
  for (unsigned long long i = 1; i <=T; i++)
  {
  	

  cin>>N;
     isFibonacci(N)? cout<<"IsFibo"<<endl:
                     cout<<"IsNotFibo"<<endl ;
  }
  return 0;
}


The output I get is correct till 5 cases, but when the 6th case comes with this input

4522240457

I get the wrong output.

Can anybody tell me what is going wrong with this input.

cire (8284)
You would need a representation with at least 67 bits to hold the result of 5*n*n when n is 4522240457. I would guess the unsigned long long data type on the target system has fewer bits.
Zhuge (4664)
What are you trying to do with the conditional operator on line 32 & 33? Just use if/else statements.

In any case, your issue is likely that 5×45222404572±4=102253293754637844245±4 won't fit in the integer type you are using.
Gamemaster007 (26)
In any case, your issue is likely that 5×45222404572±4=102253293754637844245±4 won't fit in the integer type you are using.


What should I do to get the correct output?
cire (8284)
The whole idea of the site your visiting is that you find a way to get the correct output.. So, put on your thinking cap and quit blindly googling/copying code.

How many fibonacci numbers do you suppose there are less than 1010?

[edit: typo]
Last edited on
Gamemaster007 (26)
The whole idea of the site your visiting is that you find a way to get the correct output.. So, put on your thinking cap and quit blindly googling/copying code.

The code that you see above is written by me; I haven't copied it from google.

How many fibonacci numbers do you suppose there are less than 1010?

If we take the first two numbers as 0 and 1 then the answer would be 50. The last being 7778742049
Am I correct?
cire (8284)
If we take the first two numbers as 0 and 1 then the answer would be 50. The last being 7778742049
Am I correct?


That is correct. And the number of values not being prohibitive to calculate or store should suggest an alternate algorithm to you.
Gamemaster007 (26)
That is correct. And the number of values not being prohibitive to calculate or store should suggest an alternate algorithm to you.


So my new code is: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
#include <iostream>
using namespace std;
int main(unsigned long long argc, char *argv[])
{
	unsigned long long element;
	unsigned long long j;
	unsigned long long index1,index2,mid;
	unsigned long long num1=0,num2=1,fb;
	unsigned long long array[50];
	array[0]=0;
	array[1]=1;
	for(unsigned long long i=2;i<50;i++)
	{
		fb=num1+num2;
		array[i]=fb;
		num1=num2;
		num2=fb;
		
		
	}
	index1=0;
	index2=49;
	/*for(unsigned long long i=0;i<50;i++)
	{
		
		cout<<array[i]<<endl;	
		
	}*/
	unsigned long long t;
	unsigned long long  n;
	cin>>t;
	for(unsigned long long i=1;i<=t;i++)
	{
		index1=0;
	index2=49;
		cin>>n;
	
		for(j=0;j<=49;j++)
	{
		mid=(index1+index2)/2;
		if(n>array[mid])
		{
			index1=mid+1;
		//	cout<<"Echo"<<endl;
		}
		else if(n<array[mid])
		{
			index2=mid-1;
		//	cout<<"Echo"<<endl;
		}
		else if(n==array[mid])
		{
			cout<<"IsFibo"<<endl;
			break;
		}
	
		
	}
		if(j==50)
		{
			cout<<"IsNotFibo"<<endl;
	

		}
		
	}
	
	return 0;
}


Still it's showing the wrong output.
I wrote a code to generate all the Fibonacci numbers from 0 to 50
And I found that 4522240457 is not even a Fibonacci number.

My question is why does the hackerrank's output shows 4522240457 as a Fibonacci number?

I really need help for this algorithm.

cire (8284)
My question is why does the hackerrank's output shows 4522240457 as a Fibonacci number?

My question is: What makes you think it does?
Gamemaster007 (26)
My question is: What makes you think it does?


Well, that's because we can buy and see the input and correct output of each test cases.
cire (8284)
Well, that's because we can buy and see the input and correct output of each test cases.


The input file has one more line than the output file. Reading the problem description will tell you why.

Do you still think your assertion is true?
Gamemaster007 (26)
Do you still think your assertion is true?


I feel like a complete idiot now. All I needed was to realize that the lines in input and output are different. Also I increased my size of the array to accommodate larger inputs. After doing this my code passed all test cases.

Thanks cire. You really helped me.


Topic archived. No new replies allowed.