Solving a problem in coding contest I came across a problem, which on digging a bit lead me to the data set in this question . Since the program to enumerate and finding the solution was too complex and execution time was below par I jot down the logic to the equation of curve (a single line)
Upon further digging deep I found that I missed the series which was forming a Fibonacci Series, hence by Binet's fourmla I found the nth term of the series which was even efficient. Here is the code
import math import sys def powLF(n): if n == 1: return (1, 1) L, F = powLF(n//2) L, F = (L**2 + 5*F**2) >> 1, L*F if n & 1: return ((L + 5*F)>>1, (L + F) >>1) else: return (L, F) def fib(n): if n & 1: return powLF(n) else: L, F = powLF(n // 2) return L * F def sum_digits(n): r = 0 while n: r, n = r + n % 10, n // 10 return r def _print(string): fo = open("output.txt", "w+") fo.write(string) fo.close() try: f = open('input.txt') except IOError: _print("error") sys.exit() num = f.readline() try: val = int(num) except ValueError: _print("error") sys.exit() sum = sum_digits(int(num)) f.close() if (sum == 2): _print("1") else: _print(str(int(math.ceil(fib(sum)))))
Although still the code doesn't seem to match the par criteria, how can I optimize the code further ?