In the problem of AMIFIB i have used unsigned long long to store even 1000 digit fibonacci numbers even though the range of unsigned long long is 0 to 18,446,744,073,709,551,615.How can it be possible?
Use string to represent the number.
You have used a array to keep digits of the series knowingly/unknowingly.
Thus it is just like an array which is of max. 1000 size (acc. to problem statement) , elements of type unsigned long long. Thus, you got AC.
You can read a little bit more about set header file from here :
If you are using Java or Python, then support for very large numbers is inbuilt and you dont need strings.
@skbly I remember now. There is a method which uses unsigned long long to solve this problem which was described in the editorial.
The range of unsigned long long is from 0 to 18,446,744,073,709,551,615. Now once the number exceeds this range , it will round up to some value in this range. The idea is that because this range is too big each fibonacci number will round up to some value in this range. This is something like hashing the fibonacci numbers using modulo with the upper limit of ULL. Because you are taking modulo with very large number and number of fibonacci numbers is also not very big(around 10000 less than 1000 digits i guess) they will be hashed and we will identify a number as fibonacci if its hashed value is present in pre-computed array.
Although it is not completely correct , it works for the test cases in this case. Ideally the problem setter should have made test cases to fail such hashing methods but it is very difficult since we can store the numbers modulo any large number.
@kcahdog he has got his solution AC, but he has used unsigned long long, so why he got AC, this is his question…
I too misunderstood the question initially…
Thanks!Now I understand why this method worked.The test cases were also favourable.Thanks for reply…
I have used strings to store the numbers but I was not sure about the way I was calculating the fib numbers which are declared as unsigned long long.Thanks for reply…
Thanks for the reference.