An e-commerce website wishes to find the lucky customer who will be eligible for full value cash back. For this purpose, a number N is fed to the system. It will return another number that is calculated by an algorithm. In the algorithm, a sequence is generated, in which each number is the sum of the two proceeding numbers. Initially the sequence will have two 1’s in it. The system will return the Nth number from the generated sequence which is treated as the order ID. The lucky customer will be the one who has placed that order. Write an algorithm to help the website find the lucky customer.
Input
The input consists of an integer token, representing the number fed to the system (N).
Output
Print an integer representing the order ID of the lucky customer.
Constraints
NA
Example
Input:
8
Output:
21
Explanation:
The sequence generated by the system will be 1,1,2,3,5,8,13,21. The 8th number in the sequence is 21. The lucky customer is the one who has placed the order with order ID 21.
Solution: In C
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
int i,a[n];
a[0]=a[1]=1;
for(i=2;i<n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%d",a[n-1]);
return 0;
}Solution: In Python
num = int(input())
import math
n=(math.sqrt(5)+1)/2
x=round(math.pow(n,num)/math.sqrt(5))
print(x)Also Checkout